###################################################################### ##ANIMALS: Save this file as ANIMALS. To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read ANIMALS : # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Temple University , # #zeilberg@math.temple.edu. # ####################################################################### #ANIMALS: A PACKAGE FOR COMPUTING and CONJECTURING Generating Functions #for counting animals in strips #By Doron Zeilberger, Temple University #First Version: Dec. 21, 1999 #LAST UPDATE: Dec. 21, 1999 #The most current version is available from #http://www.math.temple.edu/~zeilberg #To use it get it first, call it `ANIMALS` then go into Maple #by typing `maple`. Then, in Maple , type `read ANIMALS;` #and see the help files by doing " ezra(); " and " ezra(function_name) "; print(`ANIMALS: A PACKAGE FOR HANDLING ANIMALS IN STRIPS`): print(`Version of Dec. 21, 1999`): print(`written by Doron Zeilberger(zeilberg@math.temple.edu).`): print(`The most current version is always available from`): print(`http://www.math.temple.edu/~zeilberg`): print(`It is one of the numerous packages accompanying Doron Zeilberger's`): print( ` article: `): print(` "SYMBOL-CRUNCHING With The TRANSFER-MATRIX Method`): print(`With Applications to `): print(` Enumerating Skinny Physical Creatures" `): lprint(``): print(`For a list of the main procedures type "ezra();" , for help with`): print(`a specific procedure, type "ezra(procedure_name);"`): print(`For a list of all the procedures (including those `): print(` not required by the user), `): print(` type: ezra1(); `): ezra:=proc() if args=NULL then print(` This is ANIMALS, a Maple package for computing generating-`): print(` functions, and series-expansions, for lattice animals`): print(` confined to a strip `): print(`It is one of the numerous packages accompanying Doron Zeilberger's`): print( ` article: "Symbol-Crunching With the Transfer-Matrix Method `): print(``): print(` For a list of all procedures type: ezra1(); `): print(`The main procedures are : `): print(` GF1, GFseries, Khaya `): elif nops([args])=1 and op(1,[args])=Alphabet then print(`Alphabet(n): The Animal-Alphabet for animals in the strip [0,n]`): elif nops([args])=1 and op(1,[args])=Followers then print(`Followers(n,Let1): All the letters in the Animal Alphabet that can`): print(`follow the letter Let1, in the Animal alphabet for strips in [0,n-1]`): elif nops([args])=1 and op(1,[args])=gf then print(`gf(n,s): The generating function for animals immersed in the`): print(`strip [0,n-1]`): elif nops([args])=1 and op(1,[args])=GF1 then print(`GF1(n,s): The generating function for animals of width<=n`): print(`i.e. the formal power series whose coeff. of s^i is the`): print(` the number of (2D site) animals with i cells and width <= n `): elif nops([args])=1 and op(1,[args])=GFseries then print(`GFseries(n,L): The list, of length L, whose k^th term`): print(`is the number of (2D site) animals `): print(`(also called fixed polyominoes), with k cells and`): print(`width<=n`): elif nops([args])=1 and op(1,[args])=GfSeriesS then print(`GfSeriesS(n,L,s): The list, of length L, whose k^th term`): print(`is the weight-enumerator of (2D site) animals `): print(`(also called fixed polyominoes), with k cells and`): print(`width=n, according to the weight s^(#letters) `): elif nops([args])=1 and op(1,[args])=GFseriesS then print(`GFseriesS(n,L,s): The list, of length L, whose k^th term`): print(`is the weight-enumerator of (2D site) animals `): print(`(also called fixed polyominoes), with k cells and`): print(`width<=n, according to the weight s^(#letters) `): elif nops([args])=1 and op(1,[args])=Khaya then print(`Khaya(L): The list , of length L, whose k^th entry is`): print(`the number of (2D) fixed polyominoes (site lattice-animals)`): print(`with k cells`): elif nops([args])=1 and op(1,[args])=KhayaWLn then print(`KhayaWLn(W,L,n): The number of (site) animals with width W, `): print(`length L and n cells `): elif nops([args])=1 and op(1,[args])=LeftLetters then print(`LeftLetters(a,b): All the possible letters, in the ANIMAL alphabet`): print(`that can be the left-most letter in an animal-word`): elif nops([args])=1 and op(1,[args])=MarCha then print(`MarCha(n): The Markov Chain corresponding to`): print(`the langauge of Animals inside the strip [0,n]`): print(`It given in terms of LeftLetters,RightLetters`): print(`List of Neigbor-Sets, and List of wts,`): print(`where the letters are labeled by 1..nops(Alphabet)`): elif nops([args])=1 and op(1,[args])=PreLeftLetters then print(`PreLeftLetters(a,b): All the possible sets of closed intervals`): print(`{[a1,b1],[a2,b2],...,[ak,bk]},a<=a1<=b1<gu2 do gu1:=gu2: gu2:=FollowersS(n,gu2): od: gu2: end: ##Comp(G,V): Given a graph G, with a vertex set V #finds the set-partition on V induced by the connected #componets of G Comp:=proc(G,V) local gu,v,V1,lu: V1:=V: gu:={}: while V1<>{} do v:=V1[1]: lu:=ConComp(G,v): gu:=gu union {lu}: V1:=V1 minus lu: od: gu: end: #Sakhen(G,S): Given a graph G and a subset of its vertices #returns S and all the neighbors (only used in ConComp) Sakhen:=proc(G,S) local i,gu: gu:=S: for i from 1 to nops(S) do gu:=gu union G[S[i]]: od: gu: end: ##ConComp(G,v): Given a graph G, which is given in terms #of its adjacency table, and a vertex v finds the connencted #component that v belons to ConComp:=proc(G,v) local G1,G2: G1:={}: G2:={v}: while G1<>G2 do G1:=G2: G2:=Sakhen(G,G2): od: G2: end: #Followers(Let1): All the letters in the Animal Alphabet that can #follow the letter Let1 Followers:=proc(n,Let1) local mu,gu,ku,i: option remember: mu:=PreLeftLetters(0,n-1) minus {{}}: gu:={}: for i from 1 to nops(mu) do ku:=PreLetToLet(Let1,mu[i]): if ku<>0 then gu:=gu union {ku}: fi: od: gu: end: #FollowersS(n,S): the union of all the followers of the set #of letters of S FollowersS:=proc(n,S) local gu,i: gu:=S: for i from 1 to nops(S) do gu:=gu union Followers(n,S[i]): od: gu: end: #gf(n,s): The generating function for animals immersed in the #strip [0,n-1] gf:=proc(n,s) option remember:SolveMC1(MarCha(n),s):end: #GF1(n,s): The generating function for animals of width<=n GF1:=proc(n,s) normal(gf(n,s)-gf(n-1,s)):end: #gfSeries(n,L): The list, of length L, whose k^th term #is the number of (2D site) animals #(also called fixed polyominoes), with k cells and #immersed in the strip [0,n-1] gfSeries:=proc(n,L) option remember:SolveMC1series(MarCha(n),L):end: #GFseries(n,L): The list, of length L, whose k^th term #is the number of (2D site) animals #(also called fixed polyominoes), with k cells and #width<=n GFseries:=proc(n,L) local lu1,lu2,i: if n=1 then RETURN(gfSeries(n,L)):fi: lu1:=gfSeries(n,L):lu2:=gfSeries(n-1,L):seq(lu1[i]-lu2[i],i=1..L):end: #gfSeriesS(n,L,s): The list, of length L, whose k^th term #is the weight-enumerator of (2D site) animals #(also called fixed polyominoes), with k cells and #immersed in the strip [0,n-1], according to the weight s^(number of letters) # gfSeriesS:=proc(n,L,s) option remember:SolveMC1seriesS(MarCha(n),L,s):end: #GfSeriesS(n,L,s): The list, of length L, whose k^th term #is the weight-enumerator of (2D site) animals #(also called fixed polyominoes), with k cells and #width=n, according to the weight s^(number of letters) # GfSeriesS:=proc(n,L,s) local lu1,lu2,i: if n=1 then RETURN(GFseriesS(1,L,s)):fi: lu1:=GFseriesS(n,L,s):lu2:=GFseriesS(n-1,L,s):seq(lu1[i]-lu2[i],i=1..L):end: #GFseriesS(n,L,s): The list, of length L, whose k^th term #is the weight-enumerator of (2D site) animals #(also called fixed polyominoes), with k cells and #width<=n, according to the weight s^(number of letters) # GFseriesS:=proc(n,L,s) local lu1,lu2,i: if n=1 then RETURN(gfSeriesS(1,L,s)):fi: lu1:=gfSeriesS(n,L,s):lu2:=gfSeriesS(n-1,L,s):seq(lu1[i]-lu2[i],i=1..L):end: #Khaya(L): The list , of length L, whose k^th entry is #the number of (2D) fixed polyominoes (site lattice-animals) #with k cells Khaya:=proc(L) local n,s,w,gu,tot,TOT,i: for n from 1 to (L+1)/2 do gu[n]:=GfSeriesS(n,L,s): od: TOT:=[]: for i from 1 to L do tot:=0: for n from 1 to (L+1)/2 do tot:=tot+coeff(gu[n][i],s,n): for w from n+1 to L do tot:=tot+2*coeff(gu[n][i],s,w): od: od: TOT:=[op(TOT),tot]: od: TOT: end: #KhayaWLn(W,L,n): The number of (site) animals with width W, length L #and n cells KhayaWLn:=proc(W,L,n): coeff(GfSeriesS(W,n,s)[n],s,L): end: #LeftLetters(a,b): All the possible letters, in the ANIMAL alphabet #that can be the left-most letter in an animal-word LeftLetters:=proc(a,b) local i,gu,mu,gu1,j: option remember: mu:=PreLeftLetters(a,b) minus {{}}: gu:={}: for i from 1 to nops(mu) do gu1:=op(i,mu): gu:={op(gu),{seq({gu1[j]},j=1..nops(gu1))} }: od: gu: end: #MarCha(n): The Markov Chain corresponding to #the langauge of Animals inside the strip [0,n] #It given in terms of LeftLetters,RightLetters #List of Neigbor-Sets, and List of wts, #where the letters are labeled by 1..nops(Alphabet) MarCha:=proc(n) local gu,i,N,T,Left0,Left1,Right1,mu,mu1,j,Wts: option remember: gu:=Alphabet(n): gu:=convert(gu,list): N:=nops(gu): for i from 1 to N do T[gu[i]]:=i: od: Left0:=LeftLetters(0,n-1): Left1:={}: Right1:={}: for i from 1 to N do if nops(gu[i])=1 then Right1:=Right1 union {i}: fi: if member(gu[i],Left0) then Left1:=Left1 union {i}: fi: od: mu:=[]: for i from 1 to N do mu1:=Followers(n,gu[i]): mu:=[op(mu),{seq(T[mu1[j]],j=1..nops(mu1))}]: od: Wts:=[seq(Weight(gu[i]),i=1..nops(gu))]: [Left1,Right1,mu,Wts]: end: #PreLeftLetters(a,b): All the possible sets of `closed intervals' #{[a1,b1],[a2,b2],...,[ak,bk]} with a<=a1<=b1<b then RETURN({}): fi: if a=b then RETURN({{[a,a]},{}}): fi: gu:=PreLeftLetters(a,b-1): for i from a to b do mu1:=[i,b]: gu:=gu union {{mu1}}: gu1:=PreLeftLetters(a,i-2): for j from 1 to nops(gu1) do gu:=gu union {gu1[j] union {mu1}}: od: od: gu: end: #PreLetToLet(Let1,PreLet1) Given an Animal letter Let1, and #a preletter, PreLet1 following it, returns 0 if it PreLet1 #cannot follow Let1, and otherwise makes PreLet1 into a letter #by grouping the various boards (intervals) into sets #this making a (non-crossing) set-partition of intervals # PreLetToLet:=proc(Let1,PreLet1) local i,j,T,S,G: for i from 1 to nops(Let1) do T[Let1[i]]:={}: od: for i from 1 to nops(PreLet1) do S[PreLet1[i]]:={}: od: for i from 1 to nops(Let1) do for j from 1 to nops(PreLet1) do if Support(Let1[i]) intersect Support({PreLet1[j]})<>{} then T[Let1[i]]:=T[Let1[i]] union {PreLet1[j]}: S[PreLet1[j]]:=S[PreLet1[j]] union {Let1[i]}: fi: od: od: for i from 1 to nops(Let1) do if T[Let1[i]]={} then RETURN(0): fi: od: for i from 1 to nops(PreLet1) do G[PreLet1[i]]:={}: od: for i from 1 to nops(PreLet1) do for j from i+1 to nops(PreLet1) do if S[PreLet1[i]] intersect S[PreLet1[j]]<>{} then G[PreLet1[i]]:= G[PreLet1[i]] union {PreLet1[j]}: G[PreLet1[j]]:= G[PreLet1[j]] union {PreLet1[i]}: fi: od: od: Comp(G,PreLet1): end: #SolveMC1(MC,s): The generating function for all walks #on the Markov-Chain MC=[LeftLetters,RightLetters,Neighs,Wts] #that start with a left-Letter and ends with a right-Letter #and the wt. of a path is the product of the weights of #the visited vertices SolveMC1:=proc(MC,s) local eq,var,i,LL,RL,Nei,Wts,N,eq1,A,lu,j,Sakh,mu: LL:=MC[1]:RL:=MC[2]:Nei:=MC[3]:Wts:=MC[4]: N:=nops(Wts): eq:={}: var:={}: for i from 1 to N do var:=var union {A[i]}: if member(i,RL) then eq1:=A[i]-s^Wts[i]: else eq1:=A[i]: fi: lu:=0: Sakh:=Nei[i]: for j from 1 to nops(Sakh) do lu:=lu+A[Sakh[j]]: od: eq1:=eq1-s^Wts[i]*lu: eq:=eq union {eq1}: od: var:=solve(eq,var): mu:=0: for i from 1 to nops(LL) do mu:=mu+subs(var,A[LL[i]]): od: normal(mu): end: #SolveMC1series(MC,L): The first L terms in the sequence #enumerating the number of words of weight n (or t^n) #(depending on your def. of weight) in the Markov #Chain [LeftLetters,RightLetters,NeighborLists,WtList] #that start in one of the left-letters and ends in #one of the right-letters SolveMC1series:=proc(MC,L) local LL,RL,Nei,Wts,N,MW,A,TOT,cur,Sakh,i,j,k,tot,sa: LL:=MC[1]:RL:=MC[2]:Nei:=MC[3]:Wts:=MC[4]: N:=nops(Wts): MW:=max(op(Wts)): TOT:=[]: for i from 1 to N do A[i]:=[seq(0,j=1..MW)]: od: for j from 1 to L do for i from 1 to N do if member(i,RL) and Wts[i]=j then cur[i]:=1: else cur[i]:=0: fi: Sakh:=Nei[i]: for k from 1 to nops(Sakh) do sa:=Sakh[k]: cur[i]:=cur[i]+A[sa][MW-Wts[i]+1]: od: od: tot:=0: for i from 1 to nops(LL) do tot:=tot+cur[LL[i]]: od: TOT:=[op(TOT),tot]: for i from 1 to N do A[i]:=[op(2..MW,A[i]),cur[i]]: od: od: TOT: end: #SolveMC1seriesS(MC,L,s): The first L terms in the sequence #weight-enumerating the number of words of weight n (or t^n) #(depending on your def. of weight) in the Markov #Chain [LeftLetters,RightLetters,NeighborLists,WtList] #that start in one of the left-letters and ends in #one of the right-letters #according to the weight: number of letters SolveMC1seriesS:=proc(MC,L,s) local LL,RL,Nei,Wts,N,MW,A,TOT,cur,Sakh,i,j,k,tot,sa: LL:=MC[1]:RL:=MC[2]:Nei:=MC[3]:Wts:=MC[4]: N:=nops(Wts): MW:=max(op(Wts)): TOT:=[]: for i from 1 to N do A[i]:=[seq(0,j=1..MW)]: od: for j from 1 to L do for i from 1 to N do if member(i,RL) and Wts[i]=j then cur[i]:=s: else cur[i]:=0: fi: Sakh:=Nei[i]: for k from 1 to nops(Sakh) do sa:=Sakh[k]: cur[i]:=expand(cur[i]+s*A[sa][MW-Wts[i]+1]): od: od: tot:=0: for i from 1 to nops(LL) do tot:=tot+cur[LL[i]]: od: TOT:=[op(TOT),tot]: for i from 1 to N do A[i]:=[op(2..MW,A[i]),cur[i]]: od: od: TOT: end: #Support(Comp): Gives the set supported by the component Comp Support:=proc(Comp) local i,j: {seq( op([seq(j,j=Comp[i][1]..Comp[i][2])]), i=1..nops(Comp))}:end: #Weight(LET1): The weight of the letter Let1 Weight:=proc(LET1) local gu,i: gu:=0: for i from 1 to nops(LET1) do gu:=gu+nops(Support(LET1[i])): od: gu: end: