###################################################################### ##KamaEtzim: Save this file as KamaEtzim # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read KamaEtzim # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg at math dot rutgers dot edu # ###################################################################### #Created: March 30, 2011 print(`Created: March 30, 2011`): print(` This is KamaEtzim `): print(`It accompanyies the article `): print(`Automatic Generation of `): print(`Generating Functions for Enumerating the Number of Spanning trees`): print(`for Grid Graphs (and much more general creatures) of fixed `): print(`(but arbitrary!) width `): print(`by Shalosh B. Ekhad and Doron Zeilberger`): print(`The article is exclusively published in the Personal Journal of`): print(`Shalosh B. Ekhad and Doron Zeilberger `): print(` http://www.math.rutgers.edu/~zeilberg/pj.html `): print(`and arxiv.org `): print(`the direcet url being:`): print(`http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/etzim.html`): print(`Please report bugs to zeilberg at math dot rutgers dot edu`): print(``): print(`The most current version of this package `): print(` is available from`): print(`http://www.math.rutgers.edu/~zeilberg/tokhniot/KamaEtzim .`): 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(`For a list of the Story procedures type ezraS();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): 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): with(linalg): ezraS:=proc() if args=NULL then print(` The story procedures are: `): print(`SipurR `): else ezra(args): fi: end: ezra1:=proc() if args=NULL then print(` The supporting procedures are: `): print(` CBPgraph, CylGraph, GR1, GR,Mn, MTT, PathGraph `): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: GFcbp, GFcyl, GFG, GFrect, GFt , SeqMn `): print(` `): elif nops([args])=1 and op(1,[args])=CBPgraph then print(`CBPgraph(m): The path graph of width m but with all`): print(`possible edges between consecutive levels`): print(`For example, try:`): print(`CBPgraph(3);`): elif nops([args])=1 and op(1,[args])=CylGraph then print(`CylGraph(m): The cylinder-graph of width m`): print(`For example, try:`): print(`CylinderGraph(3);`): elif nops([args])=1 and op(1,[args])=GFcbp then print(`GFcbp(m,z): The generating function, in z, whose`): print(`coeff of z^n in its Maclaurin expansion would give`): print(`you the number of spanning trees in the graph of`): print(`mn vertices where the edges amongst {mi+1,...,mi+m}`): print(`are like a path of length m, and all the edges between`): print(`{mi+1,...,mi+m} and {m(i+1)+1,...,m(i+1)+m} are present`): print(`For example, try:`): print(`GFcbp(3,z);`): elif nops([args])=1 and op(1,[args])=GFcyl then print(`GFcyl(m,z): The generating function, in z, whose`): print(`coeff of z^n in its Maclaurin expansion would give`): print(`you the number of spanning trees in the m by n grid-graph.`): print(`For example, try:`): print(`GFcyl(3,z);`): elif nops([args])=1 and op(1,[args])=GFG then print(`GFG(G,m,z,K): Inputs a graph G on m vertices `): print(`(given as a set of edges)`): print(` a variable z and a pos. integer K`): print(`(large enough for the guessing), and outputs`): print(`the generating function (a rational function in z)`): print(`whose coefficient of z^n in its Maclaurin expansion gives`): print(`you the number of spanning trees of GxP_n. It uses`): print(`K data points for guessing.`): print(`For example, try:`): print(` GFG({{1,2},{2,3}},3,z,16); `): elif nops([args])=1 and op(1,[args])=GFrect then print(`GFrect(m,z): The generating function, in z, whose`): print(`coeff of z^n in its Maclaurin expansion would give`): print(`you the number of spanning trees in the m by n grid-graph.`): print(`For example, try:`): print(`GFrect(3,z);`): elif nops([args])=1 and op(1,[args])=GFt then print(`GFt(G,C,m,z,K): The generating function (a rational function in z)`): print(`whose coefficient of z^k in its Maclaurin expansion gives`): print(`you the number of spanning trees of Mn(G,C,m,k). It uses`): print(`K data points for guessing.`): print(`For example, try:`): print(`GFt({{1,2},{2,3}},{{1,4},{2,5},{3,6}},3,z,6);`): elif nops([args])=1 and op(1,[args])=GR then print(`GR(L,t): inputs a list L and guesses a rational`): print(`function in t`): print(`whose Maclaurin coefficients are those of L, or returns FAIL`): print(`In that case you can try and make the list,L, longer `): print(`For example, try:`): print(`GR([seq(i,i=1..10)],t);`): elif nops([args])=1 and op(1,[args])=GR1 then print(`GR1(L,t,d): inputs a list L and guesses a rational`): print(`function in t, whose denominator has degree d`): print(`whose Maclaurin coefficients are those of L`): print(`For example, try:`): print(`GR1([seq(i,i=1..10)],t,1);`): elif nops([args])=1 and op(1,[args])=Mn then print(`Mn(G,C,m,n): Given a graph G (a set of edges) on {1, ..., m}`): print(`and a biparatite graph C from {1, ..., m} to {m+1, ..., 2m}`): print(`constructs the so-called mixed product.M_n(G,C)`): print(`on {1, ..., nm}. For example, try:`): print(`Mn({{1,2}},{{1,3},{2,4}},2,3);`): elif nops([args])=1 and op(1,[args])=MTT then print(`MTT(G,n): Given a graph G on n vertices `): print(` (represented as a set of edges) `): print(` uses the Matrix Tree Theorem to find its number of `): print(` spanning trees. For example, try: `): print(` MTT({{1,2},{2,3},{1,3}},3); `): elif nops([args])=1 and op(1,[args])=PathGraph then print(`PathGraph(m): The path-graph of width m`): print(`For example, try:`): print(`PathGraph(3);`): elif nops([args])=1 and op(1,[args])=SeqMn then print(`SeqMn(G,C,m,N): The first N terms of the sequence for the`): print(`number of spanning trees of M_n(G,C,m,n) for n from 1 to N`): print(`For example, try:`): print(`SeqMn({{1,2}},{{1,3},{2,4}},2,5);`): elif nops([args])=1 and op(1,[args])=SipurR then print(`SipurR(M,z,N): the story of all generating functions for`): print(`GFrect(m,z) for m from 1 to M. displaying the first N terms`): print(`For example, try:`): print(`SipurR(3,z,30);`): else print(`There is no ezra for`,args): fi: end: #GFt(G,C,m,z,K): The generating function (a rational function in z) #whose coefficient of z^k in its Maclaurin expansion gives #you the number of spanning trees of Mn(G,C,m,k). It uses #K data points for guessing. #For example, try: #GFt({{1,2},{2,3}},{{1,4},{2,5},{3,6}},3,z,6); GFt:=proc(G,C,m,z,K) local gu,n: gu:=[seq(MTT(Mn(G,C,m,n),m*n),n=1..K)]: GR(gu,z): end: #Mn(G,C,m,n): Given a graph G (a set of edges) on {1, ..., m} #and a biparatite graph C from {1, ..., m} to {m+1, ..., 2m} #constructs the so-called mixed product.M_n(G,C) #on {1, ..., nm}. For example, try: #Mn({{1,2}},{{1,3},{2,4}},2,3); Mn:=proc(G,C,m,n) local i,j: {seq(op(subs({seq(i=i+j*m,i=1..m)},G)),j=0..n-1)} union {seq(op(subs({seq(i=i+j*m,i=1..2*m)},C)),j=0..n-2)}: end: #MTT(G,n): Given a graph G on n vertices (represented as a set of edges) #uses the Matrix Tree Theorem to find its number of #spanning trees. For example, try: #MTT({{1,2},{2,3},{1,3}},3); MTT:=proc(G,n) local M,i,j,M1,lu,mu: M:=[]: for i from 1 to n do mu:=0: M1:=[]: for j from 1 to i-1 do if member({i,j},G) then M1:=[op(M1),1]: mu:=mu+1: else M1:=[op(M1),0]: fi: od: M1:=[op(M1),lu]: for j from i+1 to n do if member({i,j},G) then M1:=[op(M1),1]: mu:=mu+1: else M1:=[op(M1),0]: fi: od: M1:=subs(lu=-mu,M1): M:=[op(M),M1]: od: M:=[seq([op(1..n-1,M[i])],i=1..n-1)]: (-1)^(n-1)*det(convert(M,matrix)): end: #SeqMn(G,C,m,N): The first N terms of the sequence for the #number of spanning trees of M_n(G,C,m,n) for n from 1 to N #For example, try: #SeqMn({{1,2}},{{1,3},{2,4}},2,5); SeqMn:=proc(G,C,m,N) local n: [seq(MTT(Mn(G,C,m,n),m*n),n=1..N)]: end: #GR1(L,t,d): inputs a list L and guesses a rational #function in t, whose denominator has degree d #whose Maclaurin coefficients are those of L #For example, try: #GR1([seq(i,i=1..10)],t,1); GR1:=proc(L,t,d) local P,Q,i,a,f,var,f1,eq: if nops(L)<2*d+4 then print(`The list must be of length at least`, 2*d+4): RETURN(FAIL): fi: f:=add(L[i]*t^i,i=1..nops(L)): Q:=add(a[i]*t^i,i=0..d): var:={seq(a[i],i=0..d)}: f1:=expand(f*Q): eq:={seq(coeff(f1,t,i),i=d+1..nops(L))}: var:=solve(eq,var): Q:=subs(var,Q): if Q=0 then RETURN(FAIL): fi: P:=expand(Q*f): P:=add(coeff(P,t,i)*t^i,i=0..nops(L)-1): f:=normal(P/Q): f1:=taylor(f,t=0,nops(L)+1): if [seq(coeff(f1,t,i),i=1..nops(L))]<>L then print(`Something is wrong!`): RETURN(FAIL): fi: f: end: #GR(L,t): inputs a list L and guesses a rational #function in t, #whose Maclaurin coefficients are those of L. If none found returns FAIL #For example, try: #GR([seq(i,i=1..10)]); GR:=proc(L,t) local d,gu: for d from 1 to trunc(nops(L)/2)-2 do gu:=GR1(L,t,d): if gu<>FAIL then RETURN(gu): fi: od: FAIL: end: #PathGraph(m): The path-graph of width m #For example, try: #PathGraph(3); PathGraph:=proc(m) local i: {seq({i,i+1},i=1..m-1)},{seq({i,i+m},i=1..m)}: end: #CylGraph(m): The cylinder-graph of width m #For example, try: #CylGraph(3); CylGraph:=proc(m) local i: {seq({i,i+1},i=1..m-1),{1,m}},{seq({i,i+m},i=1..m)}: end: #CBPgraph(m): The path graph of width m but with all #possible edges between consecutive levels #For example, try: #CBPgraph(3); CBPgraph:=proc(m) local i: {seq({i,i+1},i=1..m-1)},{seq(seq({i,j+m},i=1..m),j=1..m)}: end: #GFrect(m,z): The generating function, in z, whose #coeff of z^n in its Maclaurin expansion would give #you the number of spanning trees in the m by n grid-graph. #For example, try: #GFrect(3,z); GFrect:=proc(m,z): if not type(m,integer) or m<=1 then RETURN(FAIL): fi: GR(SeqMn(PathGraph(m),m,2^m+6),z): end: #GFcyl(m,z): The generating function, in z, whose #coeff of z^n in its Maclaurin expansion would give #you the number of spanning trees in the m by n grid-graph. #For example, try: #GFcyl(3,z); GFcyl:=proc(m,z): if not type(m,integer) or m<=1 then RETURN(FAIL): fi: GR(SeqMn(CylGraph(m),m,2^m+6),z): end: #SipurR(M,z,N): the story of all generating functions for #GFrect(m,z) for m from 1 to M. displaying the first N terms #For example, try: #SipurR(3,z,30); SipurR:=proc(M,z,N) local A,m,gu,n,f,t0,i: t0:=time(): print(`The Generating Functions for the Number of Spanning of Trees in Grid Graphs`): print(``): print(`By Shalosh B. Ekhad `): print(``): print(`This is the story of the generating functions, in `, z): print(`of the sequences enumerating the number of spanning trees`): print(`in grid-graphs P_n x P_m, for general n, and m from 2 to`,M): for m from 2 to M do gu:=GFrect(m,z): print(`Theorem: Let`, A(m,n) , `be the number of spanning trees`): print(`in the `, m, `by n grid graph, and let`): print(f(z)=Sum(A(m,n)*z^n,n=0..infinity)): print(`Then : `): print(f(z)=gu): print(``): print(`And in Maple-input format, it is:`): lprint(gu): gu:=taylor(gu,z=0,N+1): print(`The first `, N, `terms are:`): print([seq(coeff(gu,z,i),i=1..N)]): od: print(`The whole thing took`, time()-t0, `seconds.`): end: #SipurC(M,z,N): the story of all generating functions for #GFcyl(m,z) for m from 1 to M. displaying the first N terms #For example, try: #SipurC(3,z,30); SipurC:=proc(M,z,N) local B,m,gu,n,f,t0,i: t0:=time(): print(`The Generating Functions for the Number of Spanning Trees in Cylinder Graphs`): print(``): print(`By Shalosh B. Ekhad `): print(``): print(`This is the story of the generating functions, in `, z): print(`of the sequences enumerating the number of spanning trees`): print(`in cylinder-graphs P_n x C_m, for general n, and m from 2 to`,M): for m from 2 to M do gu:=GFcyl(m,z): print(`Theorem: Let`, B(m,n) , `be the number of spanning trees`): print(`in the `, m, `by n cylinder graph, and let`): print(f(z)=Sum(B(m,n)*z^n,n=0..infinity)): print(`Then : `): print(f(z)=gu): print(``): print(`And in Maple-input format, it is:`): lprint(gu): gu:=taylor(gu,z=0,N+1): print(`The first `, N, `terms are:`): print([seq(coeff(gu,z,i),i=1..N)]): od: print(`The whole thing took`, time()-t0, `seconds.`): end: #GFcbp(m,z): The generating function, in z, whose #coeff of z^n in its Maclaurin expansion would give #you the number of spanning trees in the graph of #mn vertices where the edges amongst {mi+1,...,mi+m} #are like a path of length m, and all the edges between #{mi+1,...,mi+m} and #{m(i+1)+1,...,m(i+1)+m} are present #For example, try: #GFcbp(3,z); GFcbp:=proc(m,z): if not type(m,integer) or m<=1 then RETURN(FAIL): fi: GR(SeqMn(CBPgraph(m),m,2^m+6),z): end: #GFG(G,m,z,K): Inputs a graph G on m vertices #(given as a set of edges) # a variable z and a pos. integer K #(large enough for the guessing), and outputs #the generating function (a rational function in z) #whose coefficient of z^n in its Maclaurin expansion gives #you the number of spanning trees of GxP_n. It uses #K data points for guessing. #For example, try: #GFG({{1,2},{2,3}},3,z,6); GFG:=proc(G,m,z,K) local C,i: C:={seq({i,i+m},i=1..m)}: GFt(G,C,m,z,K): end: