######################################################################
##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: