###################################################################### ##SpanningTrees.txt: Save this file as SpanningTrees.txt # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read `SpanningTrees.txt` # ##Then follow the instructions given there # ## # ##Written by Yukun Yao and Doron Zeilberger, Rutgers University # #yao at math dot rutgers dot edu; DoronZeil at gmail dot com # ###################################################################### #Created: Oct. 2018 with(linalg): print(`Created: Oct. 2018`): print(` This is SpanningTrees.txt `): print(`It is one of the packages that accompany the article `): print(`Untying The Gordian Knot via Experimental Mathematics`): print(`by Yukun Yao and Doron Zeilberger`): print(`and also available from Yao's and Zeilberger's websites`): print(``): print(`Please report bugs to DoronZeil at gmail dot com `): print(``): print(`The most current version of this package and paper`): print(` are available from`): print(`http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/gordian.html .`): print(`---------------------------------------`): print(`For a list of the Story procedures type ezraS();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`---------------------------------------`): print(`---------------------------------------`): print(`For a list of the Supporting procedures type ezra1();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`---------------------------------------`): print(`---------------------------------------`): print(`For a list of the MAIN procedures type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`---------------------------------------`): with(combinat): ezraS:=proc() if args=NULL then print(` The story procedures are: Info1v `): print(``): else ezra(args): fi: end: ezra1:=proc() if args=NULL then print(` The supporting procedures are: GridMN, GuessRGF, IndToEdge, Kn, MAT, Mat1, Mat11, Mat11N, MonoToGraph, PolyToSG `): print(``): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: Info1, fnG, PrG, PrGc, SeqST, SeqSTc, SeqS2T, SpF, SpFn `): print(` `): elif nops([args])=1 and op(1,[args])=fnG then print(`fnG(G,n,N,t): inputs a graph G on {1, ..., n} and a positive integer N, outputs`): print(`The rational generating function, in t for the number of spanning trees of Gx{1,...,N}. Try:`): print(` fnG({{1,2},{2,3}},3,20,t);`): elif nops([args])=1 and op(1,[args])=GridMN then print(`GridMN(M,N): The Grid graph {0, ..., N-1)x{0,..., M-1} followed by the list of vertices. Try:`): print(`GridMN(3,5);`): elif nops([args])=1 and op(1,[args])=GuessRGF then print(`GuessRGF(L,t): guesses a rational generating function for the sequence L starting at n=1. Try:`): print(`GuessRGF([seq(2^i+3^i,i=1..10)],t);`): elif nops([args])=1 and op(1,[args])=IndToEdge then print(`IndToEdge(M1,a): inputs an indexed expression of the form a[i,j] outputs the edge {i,j}. Try:`): print(`IndToEdge(a[4,7],a);`): elif nops([args])=1 and op(1,[args])=Info1 then print(`Info1(G,n,N,t): inputs a graph G on {1, ..., n} and a positive integer N, outputs, if possible`): print(` (i)The first N terms of the sequence number of spanning trees of Gx{1,...,N1} from N1=1 to N1=N `): print(` (ii)The first N terms of the sequence number of spanning forests with two comoments (separating 1 and n*N1) `): print(` of Gx{1,...,N1} from N1=1 to N1=N `): print(` (iii) alpha, the constant such that the former is O(alpha^N) and the latter O(N*alpha^N) `): print(` (iv) The rational generating function, in t for the number of spanning trees of Gx{1,...,N} `): print(` (v) The constant A such that the former is asymptotically A*alpha^n `): print(` (vi)The rational generating function, in t for the number of spanning forests with two components `): print(` of Gx{1,...,N} where the first and last vertices are in different components `): print(` (vii) The constant B such that the former is asymptotically B*n*alpha^n `): print(` (viii) The constant C such that the joint resistance is asymptoically C*n. Try `): print(`Info1({{1,2}},2,20,t);`): elif nops([args])=1 and op(1,[args])=Info1v then print(`Info1v(G,n,N,t): verbose version of Info1(G,n,N,t) (q.v.). Try: `): print(`Info1v({{1,2}},2,20,t);`): elif nops([args])=1 and op(1,[args])=Kn then print(`Kn(n): the complete graph on {1, ..., n}. Try:`): print(`K(5);`): elif nops([args])=1 and op(1,[args])=MAT then print(`MAT(G,n,N): The (1,1) minor of the Laplacian matrix of GxPn. Try:`): print(`MAT({{1,2},{2,3}},3,10);`): elif nops([args])=1 and op(1,[args])=Mat1 then print(`Mat1(G,n,V0,a): Given a graph G on {1,2, ...,n} described as a set of edges, and a subset of {1, .., n},`): print(`and a symbol a, finds the principal minor of Mat11(G,n,a) (q.v.)`): print(`with the members of V0 removed. Try: `): print(`Mat1({{1,2},{2,3},{3,4},{4,1}},4,{4},a);`): elif nops([args])=1 and op(1,[args])=Mat1N then print(`Mat1N(G,n,V0): Given a graph G on {1,2, ...,n} described as a set of edges, and a subset of {1, .., n},finds the principal minor of Mat11N(G,n) (q.v.)`): print(`with the members of V0 removed. Try: `): print(`Mat1N({{1,2},{2,3},{3,4},{4,1}},4,{4});`): elif nops([args])=1 and op(1,[args])=Mat11 then print(`Mat11(G,n,a): Given a graph G on {1,2, ...,n} described as a set of edges, and a symbol a, finds `): print(` the matrix whose determinant would give the Laplacian matrix, whose determinant of any n-1 by n-1 principal minor would`): print(` give the sum of the weights of all the spanning trees. Try: `): print(` Mat11({{1,2},{2,3},{3,4},{4,1}},4,a); `): elif nops([args])=1 and op(1,[args])=Mat11N then print(`Mat11N(G,n): Given a graph G on {1,2, ...,n} described as a set of edges, finds `): print(` the matrix whose determinant would give the Laplacian matrix, whose determinant of any n-1 by n-1 principal minor would`): print(` give the NUMBER of all the spanning trees. Try: `): print(` Mat11N({{1,2},{2,3},{3,4},{4,1}},4); `): elif nops([args])=1 and op(1,[args])=MonoToGraph then print(`MonoToGraph(M,a): inputs a monomial in a[i,j] and outputs the set of {i,j}-s that show up. Try:`): print(`MonoToGraph(a[1,2]*a[2,4],a);`): elif nops([args])=1 and op(1,[args])=PolyToSG then print(`PolyToSG(P,a): inputs a polynnomial in a[i,j] and outputs the set of graphs corresponding to each monomial.`): print(`PolyToSG(a[1,2]*a[2,4]+a[1,3]*a[2,5],a);`): elif nops([args])=1 and op(1,[args])=PrG then print(`PrG(G,M,N): The Cartesian product of the graph G (with M vertices {1,..., M}) and {0,1,..., N-1},`): print(` followed by the list of vertices. Try:`): print(`PrG({{1,2},{2,3}},3,5);`): elif nops([args])=1 and op(1,[args])=PrGc then print(`PrGc(G,M,N): The Cartesian product of the graph G (with M vertices {1,..., M}) and {0,1,..., N-1},`): print(`and with [0,i] connected also to [N-1,i] for each 1<=i<=M,`): print(` followed by the list of vertices. Try:`): print(`PrGc({{1,2},{2,3}},3,5);`): elif nops([args])=1 and op(1,[args])=SeqS2T then print(`SeqS2T(G,n,N): inputs a graph G on the set of vertices {1, ...,n}, and a positive integer G, outputs`): print(`the first N terms of the sequence enumerating the spanning forests of Gx{1,...,N1} with two components`): print(`where the first and last vertices belong to different components. for N1 from 1 to N`): print(`Try: `): print(` SeqS2T(Kn(4),4,10); `): elif nops([args])=1 and op(1,[args])=SeqST then print(`SeqST(G,n,N): inputs a graph G on the set of vertices {1, ...,n}, and a positive integer G, outputs`): print(`the first N terms of the sequence enumerating the spanning trees of Gx{1,...,N1} for N1 from 1 to N.`): print(`Try: `): print(`SeqST(Kn(4),4,10);`): elif nops([args])=1 and op(1,[args])=SeqSTc then print(`SeqSTc(G,n,N): inputs a graph G on the set of vertices {1, ...,n}, and a positive integer G, outputs`): print(`the first N terms of the sequence enumerating the spanning trees of Gx{1,...,N1} (closed version where N1 is connected to 1)`): print(`for N1 from 1 to N.`): print(`Try: `): print(`SeqSTc(Kn(4),4,10);`): elif nops([args])=1 and op(1,[args])=SpF then print(`SpF(G,n,V0): The set of spanning forests of the graph G with set of vertices {1, ..., n} where the members of V0 belong to different components.`): print(`Try: `): print(` SpF({{1,2},{1,3},{2,3}},3,{1}); `): elif nops([args])=1 and op(1,[args])=SpFn then print(`SpFn(G,n,V0): The NUMBER of spanning forests of the graph G with set of vertices {1, ..., n} where the members of V0 belong to different components.`): print(`Try: `): print(` SpFn({{1,2},{1,3},{2,3}},3,{1}); `): else print(`There is no ezra for`,args): fi: end: ###########From Cfinite #SeqFromRec(S,N): Inputs S=[INI,ope] #where INI is the list of initial conditions, a ope a list of #size L, say, and a recurrence operator ope, codes a list of #size L, finds the first N0 terms of the sequence satisfying #the recurrence f(n)=ope[1]*f(n-1)+...ope[L]*f(n-L). #For example, for the first 20 Fibonacci numbers, #try: SeqFromRec([[1,1],[1,1]],20); SeqFromRec:=proc(S,N) local gu,L,n,i,INI,ope: INI:=S[1]:ope:=S[2]: if not type(INI,list) or not type(ope,list) then print(`The first two arguments must be lists `): RETURN(FAIL): fi: L:=nops(INI): if nops(ope)<>L then print(`The first two arguments must be lists of the same size`): RETURN(FAIL): fi: if not type(N,integer) then print(`The third argument must be an integer`, L): RETURN(FAIL): fi: if Nexpand(SeqFromRec(S,L+1)) then print([seq(coeff(f1,t,i),i=0..L)],SeqFromRec(S,L+1)): RETURN(FAIL): else RETURN(factor(f)): fi: end: #GuessRec1(L,d): inputs a sequence L and tries to guess #a recurrence operator with constant cofficients of order d #satisfying it. It returns the initial d values and the operator # as a list. For example try: #GuessRec1([1,1,1,1,1,1],1); GuessRec1:=proc(L,d) local eq,var,a,i,n: if nops(L)<=2*d+2 then print(`The list must be of size >=`, 2*d+3 ): RETURN(FAIL): fi: var:={seq(a[i],i=1..d)}: eq:={seq(L[n]-add(a[i]*L[n-i],i=1..d),n=d+1..nops(L))}: var:=solve(eq,var): if var=NULL then RETURN(FAIL): else RETURN([[op(1..d,L)],[seq(subs(var,a[i]),i=1..d)]]): fi: end: #GuessRec(L): inputs a sequence L and tries to guess #a recurrence operator with constant cofficients #satisfying it. It returns the initial values and the operator # as a list. For example try: #GuessRec([1,1,1,1,1,1]); GuessRec:=proc(L) local gu,d: for d from 1 to trunc(nops(L)/2)-2 do gu:=GuessRec1(L,d): if gu<>FAIL then RETURN(gu): fi: od: FAIL: end: #GuessRGF(L,t): guesses a rational generating function for the sequence L starting at n=1. Try: #GuessRGF([seq(2^i+3^i,i=1..10)],t); GuessRGF:=proc(L,t) local gu: gu:=GuessRec([0,op(L)]): if gu=FAIL then RETURN(FAIL): fi: CtoR(gu,t): end: ###########End From Cfinite #Mat11(G,n,a): Given a graph G on {1,2, ...,n} described as a set of edges, finds #the matrix whose determinant would give the Laplacian matrix, whose determinant of any n-1 by n-1 principal minor would #give the sum of the weights of all the spanning trees. Try #Mat11({{1,2},{2,3},{3,4},{4,1}},4,a); Mat11:=proc(G,n,a) local M,i,j,lu: if G minus {seq(seq({i,j},i=1..j-1),j=1..n)}<>{} then print(`The set of edges`, G, `is not good `): RETURN(FAIL): fi: for i from 1 to n do lu:=0: for j from 1 to n do if i<>j and member({i,j},G) then M[i,j]:=-a[i,j]: lu:=lu+a[i,j]: else M[i,j]:=0: fi: od: M[i,i]:=lu: od: [seq([seq(M[i,j],j=1..n)],i=1..n)]: end: #Mat1(G,n,V0,a): Given a graph G on {1,2, ...,n} described as a set of edges, and a subset of {1, .., n},finds the principal minor of Mat11(G,n,a) (q.v.) #with the members of V0 removed. Try #Mat1({{1,2},{2,3},{3,4},{4,1}},{4},a); Mat1:=proc(G,n,V0,a) local i,j,gu,lu,M: M:=Mat11(G,n,a): gu:=[]: for i from 1 to n do if not member(i,V0) then lu:=[]: for j from 1 to n do if not member(j,V0) then lu:=[op(lu),M[i][j]]: fi: od: gu:=[op(gu),lu]: fi: od: gu: end: #IndToEdge(M1,a): inputs an indexed expression of the form a[i,j] outputs the edge {i,j}. Try: #IndToEdge(a[4,7],a); IndToEdge:=proc(M1,a): if not type(M1, indexed) then RETURN(FAIL): fi: if op(0,M1)<>a then RETURN(FAIL): fi: if nops(M1)<>2 then RETURN(FAIL): fi: if op(1,M1)=op(2,M1) then RETURN(FAIL): fi: {op(1,M1),op(2,M1)}: end: #MonoToGraph(M,a): inputs a monomial in a[i,j] and outputs the set of {i,j}-s that show up. Try: #MonoToGraph(a[1,2]*a[2,4],a); MonoToGraph:=proc(M,a) local i,M1,lu,gu: if type(M,indexed) then RETURN({IndToEdge(M,a)}): fi: if not type(M,`*`) then RETURN(FAIL): fi: gu:={}: for i from 1 to nops(M) do M1:=op(i,M): lu:=IndToEdge(M1,a): if lu=FAIL then RETURN(FAIL): else gu:=gu union {lu}: fi: od: gu: end: #PolyToSG(P,a): inputs a polynnomial in a[i,j] and outputs the set of graphs corresponding to each monomial. #PolyToSG(a[1,2]*a[2,4]+a[1,3]*a[2,5],a); PolyToSG:=proc(P,a) local M,gu,i,lu: if not type(P,`+`) then RETURN({MonoToGraph(P,a)}): fi: gu:={}: for i from 1 to nops(P) do M:=op(i,P): lu:=MonoToGraph(M,a): if lu=FAIL then RETURN(FAIL): else gu:=gu union {lu}: fi: od: gu: end: #SpF(G,n,V0): The set of spanning forests of the graph G with set of vertices {1, ..., n} where the members of V0 belong to different components. #Try: #SpF({{1,2},{1,3},{2,3}},3,{1}); SpF:=proc(G,n,V0) local a: PolyToSG(det(Mat1(G,n,V0,a)),a): end: #Kn(n): the complete graph on {1, ..., n}. Try: #Kn(5); Kn:=proc(n) local i,j: {seq(seq({i,j},j=i+1..n),i=1..n)}: end: #Mat11N(G,n): Given a graph G on {1,2, ...,n} described as a set of edges, finds #the matrix whose determinant would give the Laplacian matrix, whose determinant of any n-1 by n-1 principal minor would #give the number of the spanning trees. Try #Mat11N({{1,2},{2,3},{3,4},{4,1}},4); Mat11N:=proc(G,n) local M,i,j,lu: if G minus {seq(seq({i,j},i=1..j-1),j=1..n)}<>{} then print(`The set of edges`, G, `is not good `): RETURN(FAIL): fi: for i from 1 to n do lu:=0: for j from 1 to n do if i<>j and member({i,j},G) then M[i,j]:=-1: lu:=lu+1: else M[i,j]:=0: fi: od: M[i,i]:=lu: od: [seq([seq(M[i,j],j=1..n)],i=1..n)]: end: #Mat1N(G,n,V0): Given a graph G on {1,2, ...,n} described as a set of edges, and a subset of {1, .., n},finds the principal minor of Mat11N(G,n) (q.v.) #with the members of V0 removed. Try #Mat1N({{1,2},{2,3},{3,4},{4,1}},4,{4}); Mat1N:=proc(G,n,V0) local i,j,gu,lu,M: M:=Mat11N(G,n): gu:=[]: for i from 1 to n do if not member(i,V0) then lu:=[]: for j from 1 to n do if not member(j,V0) then lu:=[op(lu),M[i][j]]: fi: od: gu:=[op(gu),lu]: fi: od: gu: end: #SpFn(G,n,V0): The NUMBER of spanning forests of the graph G with set of vertices {1, ..., n} where the members of V0 belong to different components. #Try: #SpFn({{1,2},{1,3},{2,3}},3,{1}); SpFn:=proc(G,n,V0) det(Mat1N(G,n,V0)): end: #GridMN(M,N): The Grid graph {0, ..., N-1)x{0,..., M-1} followed by the list of vertices. Try: #GridMN(3,5); GridMN:=proc(M,N) local G,gu,i,j,T: G:={ #horizontal edges seq(seq({[i,j],[i+1,j]},i=0..N-2),j=0..M-1), #vertical edges seq(seq({[i,j],[i,j+1]},i=0..N-1),j=0..M-2) }: gu:=[seq(seq([i,j],j=0..M-1),i=0..N-1)]: for i from 1 to nops(gu) do T[gu[i]]:=i: od: G:=subs({seq(gu[i]=T[gu[i]],i=1..nops(gu))},G): [G,gu]: end: #PrG(G,M,N): The Cartesian product of the graph G (with M vertices {1,..., M}) and {0,1,..., N-1}, # followed by the list of vertices. Try: #PrG({{1,2},{2,3}},3,5); PrG:=proc(G,M,N) local MG,gu,i,j,T,e: MG:={ #horizontal edges seq(seq({[i,j],[i+1,j]},i=0..N-2),j=1..M), #vertical edges seq(seq({[i,e[1]],[i,e[2]] },e in G),i=0..N-1) }: gu:=[seq(seq([i,j],j=1..M),i=0..N-1)]: for i from 1 to nops(gu) do T[gu[i]]:=i: od: MG:=subs({seq(gu[i]=T[gu[i]],i=1..nops(gu))},MG): [MG,gu]: end: #PrGc(G,M,N): The Cartesian product of the graph G (with M vertices {1,..., M}) and {0,1,..., N-1}, #and with [0,i] connected also to [N-1,i] for each 1<=i<=M, # followed by the list of vertices. Try: #PrGc({{1,2},{2,3}},3,5); PrGc:=proc(G,M,N) local MG,gu,i,j,T,e: MG:={ #horizontal edges seq(seq({[i,j],[i+1,j]},i=0..N-2),j=1..M), seq({[0,j],[N-1,j]},j=1..M), #vertical edges seq(seq({[i,e[1]],[i,e[2]] },e in G),i=0..N-1) }: gu:=[seq(seq([i,j],j=1..M),i=0..N-1)]: for i from 1 to nops(gu) do T[gu[i]]:=i: od: MG:=subs({seq(gu[i]=T[gu[i]],i=1..nops(gu))},MG): [MG,gu]: end: #SeqST(G,n,N): inputs a graph G on the set of vertices {1, ...,n}, and a positive integer G, outputs #the first N terms of the sequence enumerating the spanning trees of Gx{1,...,N1} for N1 from 1 to N #Try: #SeqST(Kn(4),4,10); SeqST:=proc(G,n,N) local N1: [seq(SpFn(PrG(G,n,N1)[1],n*N1,{1}), N1=1..N)]: end: #SeqSTc(G,n,N): inputs a graph G on the set of vertices {1, ...,n}, and a positive integer G, outputs #the first N terms of the sequence enumerating the spanning trees of Gx{1,...,N1} (closed version) for N1 from 1 to N #Try: #SeqSTc(Kn(4),4,10); SeqSTc:=proc(G,n,N) local N1: [seq(SpFn(PrGc(G,n,N1)[1],n*N1,{1}), N1=2..N)]: end: #SeqS2T(G,n,N): inputs a graph G on the set of vertices {1, ...,n}, and a positive integer G, outputs #the first N terms of the sequence enumerating the spanning forests of Gx{1,...,N1} with two components #where the first and last vertices belong to different components. for N1 from 1 to N #Try: #SeqS2T(Kn(4),4,10); SeqS2T:=proc(G,n,N) local N1: [0,seq(SpFn(PrG(G,n,N1)[1],n*N1,{1,n*N1}), N1=2..N)]: end: #Info1(G,n,N,t): inputs a graph G on {1, ..., n} and a positive integer N, outputs, if possible #(i)The first N terms of the sequence number of spanning trees of Gx{1,...,N1} from N1=1 to N1=N #(ii)The first N terms of the sequence number of spanning forests with two comoments (separating 1 and n*N1) #of Gx{1,...,N1} from N1=1 to N1=N #(iii) alpha, the constant such that the former is O(alpha^N) and the latter O(N*alpha^N) #(iv) The rational generating function, in t for the number of spanning trees of Gx{1,...,N} #(v) The constant A such that the former is asymptotically A*alpha^n #(vi)The rational generating function, in t for the number of spanning forests with two components #of Gx{1,...,N} where the first and last vertices are in different components #(vii) The constant B such that the former is asymptotically B*n*alpha^n #(viii) The constant C such that the joint resistance is asymptoically C*n. Try #Info1({{1,2}},2,20,t); Info1:=proc(G,n,N,t) local H,gu,gu2,lu,lu2,alpha1, alpha2,alpha,A,B: Digits:=30: gu:=SeqST(G,n,N): gu2:=SeqS2T(G,n,N): H:=[gu,gu2]: alpha1:=evalf(gu[-1]/gu[-2]): alpha2:=evalf(gu[-2]/gu[-3]): if abs(alpha1-alpha2)>10^(-6) then print(abs(alpha1-alpha2)): RETURN(H): else alpha:=evalf(alpha1): H:=[op(H),alpha]: fi: lu:=GuessRGF(gu,t): if lu=FAIL then RETURN(H): else H:=[op(H),lu]: fi: A:=-alpha*subs(t=1/alpha,numer(lu))/subs(t=1/alpha,diff(denom(lu),t) ): H:=[op(H),A]: lu2:=GuessRGF(gu2,t): if lu2=FAIL then RETURN(H): else H:=[op(H),lu2]: fi: B:=2*alpha^2*subs(t=1/alpha,numer(lu2))/subs(t=1/alpha,diff(denom(lu2),t,t) ): H:=[op(H),B,B/A]: H: end: #Info1v(G,n,N,t): verbose version of Info1(G,n,N,t) (q.v.) #inputs a graph G on {1, ..., n} and a positive integer N, outputs, if possible #(i)The first N terms of the sequence number of spanning trees of Gx{1,...,N1} from N1=1 to N1=N #(ii)The first N terms of the sequence number of spanning forests with two comoments (separating 1 and n*N1) #of Gx{1,...,N1} from N1=1 to N1=N #(iii) alpha, the constant such that the former is O(alpha^N) and the latter O(N*alpha^N) #(iv) The rational generating function, in t for the number of spanning trees of Gx{1,...,N} #(v)The rational generating function, in t for the number of spanning forests with two components #of Gx{1,...,N} where the first and last vertices are in different components #(vi) The constant A such that the former is asymptotically A*alpha^n #(vii) The constant B such that the former is asymptotically B*n*alpha^n #(viii) The constant C such that the joint resistance is asymptoically C*n. Try #Info1({{1,2}},2,20,t); Info1v:=proc(G,n,N,t) local gu,t0,i: t0:=time(): gu:=Info1(G,n,N,t): print(``): print(`On the Number of Spanning Trees and Forests of the graph`, G, `and {1,...,n} for general n`): print(``): print(`Consider the graph, let's call it G`, G): print(``): print(`on the set of vertices`, {seq(i,i=1..n)}): print(``): print(`The first`, N, `terms of the sequence enumerating spanning trees of Gx{1,...,n} are `): print(``): print(gu[1]): print(``): print(`The first`, N, `terms of the sequence enumerating spanning forests, with two trees, of Gx{1,...,n}, where the smallest and largest vertices are in `): print(`different components (trees) are `): print(``): print(gu[2]): print(``): print(`The number of spanning trees, and 2-tree forest are O(alpha^n) and O(n alpha^n) where alpha is`, evalf(gu[3],10)): print(``): if nops(gu)>3 then print(`The generating function for the number of spanning trees is`): print(``): print(gu[4]): print(``): print(`and in Maple format:`): print(``): lprint(gu[4]): print(``): print(`From this follows that the number of spanning trees is asymptotic to A*alpha^n where A is`, evalf(gu[5],10), `and as above alpha is`, gu[3]): print(``): fi: if nops(gu)>5 then print(``): print(`The generating function for the number of spanning forests with two components, as above, is`): print(gu[6]): print(``): print(``): print(`and in Maple format:`): print(``): lprint(gu[6]): print(``): print(`From this follows that the number of spanning forests is asymptotic to B*n*alpha^n where B is`, evalf(gu[7],10), `and as above alpha is`, gu[3]): print(``): print(`hence the joint resistance, as n goes to infinity behaves like n times `, evalf(gu[8],10)): fi: print(`------------------`): print(`This ends this article that took`, time()-t0, `seconds to generate. `): end: #MAT(G,n,N): The (1,1) minor of the Laplacian matrix of GxPn. Try: #MAT({{1,2},{2,3}},3,10); MAT:=proc(G,n,N) local lu: lu:=PrG(G,n,N)[1]: Mat1N(lu,n*N,{1}): end: #fnG(G,n,N,t): inputs a graph G on {1, ..., n} and a positive integer N, outputs #The rational generating function, in t for the number of spanning trees of Gx{1,...,N} fnG:=proc(G,n,N,t) local H,gu,gu2,lu,lu2,alpha1, alpha2,alpha,A,B: Digits:=30: gu:=SeqST(G,n,N): lu:=GuessRGF(gu,t): end: