######################################################################
##FreeANIMALS: Save this file as FreeANIMALS . To use it, stay in the#
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read FreeANIMALS : <Enter>                         #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Doron Zeilberger, Temple University ,                   #
#zeilberg@math.temple.edu.                                           # 
#######################################################################
 
 
#FreeANIMALS: 
# A PACKAGE FOR COMPUTING and CONJECTURING Generating Functions
#for counting (2D site) animals with vertical-cross-sections of bounded width
#By Doron Zeilberger, Temple University <zeilberg@math.temple.edu>
 
#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(`FreeANIMALS: ANOTHER PACKAGE FOR HANDLING (2D site) animals `):
 print(` a.k.a. fixed polyominoes `):
 print(` Unlike ANIMALS, we only restrict the width of`):
 print(`vertical cross-sections.`):
 print(`Version of Dec. 23, 1999`):
 print(`written by Doron Zeilberger(zeilberg@math.temple.edu).`):
 print(`This is one of the packages accompanying Doron Zeilberger's`):
 print(` article: Symbol-Crunching with the Transfer-Matrix Method.`):
 print(``):
 print(`The most current version is always available from`):
 print(`http://www.math.temple.edu/~zeilberg/`):
 print(`For a list of the main procedures type "ezra();", for help with`):
 print(`a specific procedure, type "ezra(procedure_name);"`):
 
 
ezra1:=proc()
if args=NULL then
 print(`Contains the following procedures: Alphabet, Followers, gf,`):
 print(`  gfList, gfSeries, gfSeriesList, gfSeriesS, HeightenComp,`):
 print(` HeightenLetter `):
  print(` LeftLetters, ListToMultiSet, MarCha, NormalizeLetter,`):
  print(`     PreLeftLetters, PreLetToLet, SolveMC2 ,`):
  print(` SolveMC2series, SolveMC2seriesS, Weight `):
 print(`For instructions type ezra(proc_names)`):
fi:
end:
 
ezra:=proc()
if args=NULL then
  print(`This is FreeANIMALS, one of the packages accompanying`):
  print(` Doron Zeilberger's`):
 print(` article: Symbol-Crunching with the Transfer-Matrix Method`):
 print(``):
 print(`The Main procedures are: `):
 print(`  gf, gfList, gfSeries, gfSeriesList `):
 print(``):
 print(`For a list of ALL procedures type "ezra1();" `);
 print(`For help with a procedure: type "ezra(procedure_name);"`):
 print(` For example, for help with gf, type: "ezra(gf);" `):
 
 
elif nops([args])=1 and op(1,[args])=Alphabet then
print(`Alphabet(n): The Animal-Alphabet for animals in the strip [0,n-1]`):
 
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])=HeightenComp then
print(`HeightenComp(Comp,h): given a component (or pre-letter)`):
print(`raises it by h (h may be negative of-course)`):
 
elif nops([args])=1 and op(1,[args])=HeightenLetter then
print(`HeightenLetter(LET,h): given a Letter, LET,`):
print(`raises it by h (h may be negative of-course)`):
 
elif nops([args])=1 and op(1,[args])=gf then
print(`gf(n,s): Given a positive integer n, and a variable s`):
print(` The generating function, in the variable s, whose coefficient`):
print(`of s^k is the number of animals with k cells`):
print(` each of whose vertical cross-sections has height<=n `):
print(`For example: gf(1,t) should be 1/(1-t) `):
 
elif nops([args])=1 and op(1,[args])=gfList then
print(`gfList(resh,s): The generating function , in the variable s,`):
print(`for animals `):
print(`each of whose vertical cross-sections with i components `):
print(`has height<=resh[i], for i=1,2,..., nops(resh)`):
 
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(` each of whose vertical cross-sections has height<=n `):
 
elif nops([args])=1 and op(1,[args])=gfSeriesList then
print(`gfSeriesList(resh,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(`each of whose vertical cross-sections with i components `):
print(`has height<=resh[i], for i=1,2,...,nops(resh)`):
 
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(` each of whose vertical cross-sections has height<=n `):
 
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])=ListToMultiSet then
print(`ListToMultiSet(resh): given a list of items, resh,`):
print(`converts it to a multi-set with the data structure`):
print(`{[a1,n1],[a2,n2], [ak,nk]}, meaning that a1 showed `):
print(`up n1 times, a2, showed up n2 times , ...`):
 
elif nops([args])=1 and op(1,[args])=MarCha then
print(`MarCha(n): The Markov Chain (with multiplicities, corresponding to`):
print(`the langauge of Animals inside the strip [0,n-1]`):
print(`It is 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])=MarChaList then
print(`MarChaList(resh): The Markov Chain (with multipliticies) `):
print(`corresponding to the langauge of Animals accodring to the list resh.`):
print(`Where the allowed letters are of width<=resh[i] if it has i`):
print(` components (boards) for i=1..nops(resh). `):
print(` It is 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])=NormalizeLetter then
print(`NormalizeLetter(LET): Given a letter LET, heightens or lowers it`):
print(`so that its lowest point is 0`):
 
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<<a2<=b2<<a3..<<ak<=bk<=b`):
 
elif nops([args])=1 and op(1,[args])=PreLetToLet then
print(`PreLetToLet(Let1,PreLet1) Given an Animal letter Let1, and`):
print(`a preletter, PreLet1 following it, returns 0 if it PreLet1`):
print(`cannot follow Let1, and otherwise makes PreLet1 into a letter`):
print(`by grouping the various boards (intervals) into sets`):
print(`this making a (non-crossing) set-partition of intervals`):
 
elif nops([args])=1 and op(1,[args])=SolveMC2 then
print(`SolveMC2(MC,s): The generating function for all walks`):
print(`on the General Markov-Chain MC=[LeftLetters,RightLetters,Neighs,Wts]`):
print(`that start with a left-Letter and ends with a right-Letter`):
print(`and the wt. of a path is the product of the weights of`):
print(`the visited vertices `):
 
elif nops([args])=1 and op(1,[args])=SolveMC2series then
print(`SolveMC2series(MC,L): The first L terms in the sequence`):
print(`enumerating the number of words of weight n (or t^n)`):
print(`(depending on your def. of weight) in the General Markov`):
print(`Chain [LeftLetters,RightLetters,NeighborLists,WtList]`):
print(`that start in one of the left-letters and ends in`):
print(`one of the right-letters`):
 
 
elif nops([args])=1 and op(1,[args])=SolveMC2seriesS then
print(`SolveMC2seriesS(MC,L,s): The first L terms in the sequence`):
print(`weight-enumerating the number of words of weight n (or t^n)`):
print(`also according to the weigth: s^(number of letters)`):
print(`(depending on your def. of weight) in the General Markov`):
print(`Chain [LeftLetters,RightLetters,NeighborLists,WtList]`):
print(`that start in one of the left-letters and ends in`):
print(`one of the right-letters`):
 
elif nops([args])=1 and op(1,[args])=Weight then
print(`Weight(LET1): The weight of the letter Let1`):
 
else
print(`There is no ezra item for`,args[1]):
fi:
 
end:
 
#Alphabet(n): The Animal-Alphabet for animals in the strip [0,n-1]
Alphabet:=proc(n)
local gu1,gu2:
gu1:={}:
gu2:=LeftLetters(0,n-1):
while gu1<>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,mu1,h:
option remember:
mu:=PreLeftLetters(0,n-1):
gu:=[]:
 
for i from 1 to nops(mu) do
for h from -(n-1) to n-1 do
mu1:=HeightenComp(mu[i],h):
ku:=PreLetToLet(Let1,mu1):
if ku<>0 then
 gu:=[op(gu),NormalizeLetter(ku)]:
fi:
od:
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 convert(Followers(n,S[i]),set):
od:
gu:
end:
 
#gf(n,s): The generating function for animals immersed in the
#each of whose vertical cross-sections has height<=n
gf:=proc(n,s) option remember:factor(SolveMC2(MarCha(n),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
#whose vertical cross-sections has height<=n
gfSeries:=proc(n,L) :
SolveMC2series(MarCha(n),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:SolveMC2seriesS(MarCha(n),L,s):end:
 
 
#HeightenComp(Comp,h): given a component (or pre-letter)
#raises it by h (h may be negative of-course)
HeightenComp:=proc(Comp1,h) local i: 
{seq([Comp1[i][1]+h,Comp1[i][2]+h],i=1..nops(Comp1))}: end:
 
 
#HeightenLetter(LET,h): given a Letter, LET,
#raises it by h (h may be negative of-course)
HeightenLetter:=proc(LET1,h) local i: 
{seq(HeightenComp(LET1[i],h),i=1..nops(LET1))}: 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:
 
#ListToMultiSet(resh): given a list of items, resh,
#converts it to a multi-set with the data structure
#{[a1,n1],[a2,n2], [ak,nk]}, meaning that a1 showed 
#up n1 times, a2, showed up n2 times , ...
ListToMultiSet:=proc(resh)
local kv,i,T:
kv:=convert(resh,set):
 
for i from 1 to nops(kv) do
T[kv[i]]:=0:
od:
 
for i from 1 to nops(resh) do
T[resh[i]]:=T[resh[i]]+1:
od:
 
{seq([kv[i],T[kv[i]]],i=1..nops(kv))}:
end:
 
 
 
#MarCha(n): The Markov Chain (with multipliticies) corresponding to
#the langauge of Animals inside the strip [0,n-1]
#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:=ListToMultiSet(Followers(n,gu[i])):
 mu:=[op(mu),{seq([T[mu1[j][1]],mu1[j][2]],j=1..nops(mu1))}]:
od:
 
Wts:=[seq(Weight(gu[i]),i=1..nops(gu))]:
 
[Left1,Right1,mu,Wts]:
end:
 
#NormalizeLetter(LET): Given a letter LET, heightens or lowers it
#so that its lowest point is 0
NormalizeLetter:=proc(LET1)
local m,i:
m:=min(seq(op(Support(LET1[i])),i=1..nops(LET1))):
HeightenLetter(LET1,-m):
end:
 
#PreLeftLetters(a,b): All the possible sets of `closed intervals'
#{[a1,b1],[a2,b2],...,[ak,bk]} with a<=a1<=b1<<a2<=b2<<a3..<<ak<=bk<=b
PreLeftLetters:=proc(a,b)
local gu,i,mu1,gu1,j:
option remember:
 
if not type(a,integer) or not type(b, integer) then
ERROR(`Bad input`):
fi:
if a>b then
RETURN({}):
fi:
 
if a=b then
RETURN({{[a,a]}}):
fi:
 
gu:=PreLeftLetters(a,b-1) union {{[a,b]}}:
 
for i from a to b do
mu1:=[i,b]:
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:
 
 
#SolveMC2(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 
SolveMC2:=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+Sakh[j][2]*A[Sakh[j][1]]:
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:
 
 
#SolveMC2series(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 General Markov
#Chain [LeftLetters,RightLetters,NeighborLists,WtList]
#that start in one of the left-letters and ends in
#one of the right-letters
SolveMC2series:=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]+sa[2]*A[sa[1]][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:
 
 
#SolveMC2seriesS(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
SolveMC2seriesS:=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]+sa[2]*s*A[sa[1]][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:
 
 
#########Section with More Refined Alphabet
 
ezraR:=proc()
if args=NULL then
 print(`Contains the following procedures: FollowersList, gfList, `):
print(` gfSeriesList, LeftLettersList,PreLeftLettersk, MarChaList `):
 
elif nops([args])=1 and op(1,[args])=FollowersList then
print(`FollowersList(Let1,resh): All the letters in the Animal `):
print(`Alphabet that can`):
print(`follow the letter Let1, where we only consider letters with`):
print(`1 boards with width <=resh[1], with 2 boards with`):
print(` width<=resh[2], etc.`):
 
elif nops([args])=1 and op(1,[args])=gfList then
print(`gfList(resh,s): The generating function, in variable s, for animals `):
print(`each of whose vertical cross-sections with i components `):
print(`has height<=resh[i], for i=1,2,..nops(resh)`):
 
elif nops([args])=1 and op(1,[args])=gfSeriesList then
print(`gfSeriesList(resh,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(`each of whose vertical cross-sections with i components `):
print(`has height<=resh[i], for i=1,2,..nops(resh)`):
 
elif nops([args])=1 and op(1,[args])=LeftLettersList then
print(`LeftLettersList(resh): All the possible  letters, in the ANIMAL`):
print(` alphabet such that those with one component have width<=resh[1],`):
print(`those with two components have width<=resh[2] etc.`):
 
elif nops([args])=1 and op(1,[args])=MarChaList then
print(`MarChaList(resh): The Markov Chain (with multipliticies)`):
print(` corresponding to `):
print(`the langauge of Animals accodring to the list resh`):
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])=PreLeftLettersk then
print(``):
print(`PreLeftLettersk(a,b,k): All the possible sets of closed intervals`):
print(`{[a1,b1],[a2,b2],...,[ak,bk]} with `):
print(`a<=a1<=b1<<a2<=b2<<a3..<<ak<=bk<=b`):
 
else
print(`No help`):
fi:
end:
 
 
#AlphabetList(resh): The Animal-Alphabet for animals 
#according to the list resh
AlphabetList:=proc(resh)
local gu1,gu2:
gu1:={}:
gu2:=LeftLettersList(resh):
while gu1<>gu2 do
gu1:=gu2:
gu2:=FollowersSList(gu2,resh):
od:
gu2:
end:
 
#Gova(Let1): The height of the letter Let1
Gova:=proc(Let1)
local lu,i:
lu:={}:
for i from 1 to nops(Let1) do
lu:=lu union Support(Let1[i]):
od:
max(op(lu))+1:
end:
 
 
#Gova1(PreLet1): The height of the Preletter PreLet1
Gova1:=proc(PreLet1)
local lu:
lu:=Support(PreLet1):
max(op(lu))+1:
end:
 
#FollowersList(Let1,resh): All the letters in the Animal Alphabet that can
#follow the letter Let1, where we only consider letters with
#1 boards with width <=resh[1], with 2 boards with width<=resh[2], etc.
FollowersList:=proc(Let1,resh)
local mu,gu,ku,i,mu1,h,n:
option remember:
n:=Gova(Let1):
mu:=PreLeftLettersList(resh):
gu:=[]:
 
for i from 1 to nops(mu) do
for h from -(Gova1(mu[i])-1) to n-1 do
mu1:=HeightenComp(mu[i],h):
ku:=PreLetToLet(Let1,mu1):
if ku<>0 then
 gu:=[op(gu),NormalizeLetter(ku)]:
fi:
od:
od:
 
gu:
end:
 
 
#FollowersSList(S,resh): the union of all the followers of the set
#of letters of S, according to the list resh
FollowersSList:=proc(S,resh)
local gu,i:
gu:=S:
 
for i from 1 to nops(S) do
 gu:=gu union convert(FollowersList(S[i],resh),set):
od:
gu:
end:
 
 
#gfList(resh,s): The generating function , in the variable s,
#for animals 
#each of whose vertical cross-sections with i components 
#has height<=resh[i], for i=1,2,..nops(resh)
gfList:=proc(resh,s) option remember:SolveMC2(MarChaList(resh),s):end:
 
#gfSeriesList(resh,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
#each of whose vertical cross-sections with i components 
#has height<=resh[i], for i=1,2,..nops(resh)
gfSeriesList:=proc(resh,L) :
SolveMC2series(MarChaList(resh),L):
end:
 
#LeftLettersList(resh): All the possible  letters, in the ANIMAL alphabet
#such that those with one component have width<=resh[1],
#those with two components have width<=resh[2] etc.
LeftLettersList:=proc(resh)
local i,gu,mu,gu1,j,i1:
option remember:
 
mu:={}:
for i1 from 1 to nops(resh) do
mu:=mu union PreLeftLettersk(0,resh[i1]-1,i1):
od:
 
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:
 
 
 
#MarChaList(resh): The Markov Chain (with multipliticies) corresponding to
#the langauge of Animals accodring to the list resh
#It given in terms of LeftLetters,RightLetters
#List of Neigbor-Sets, and List of wts,
#where the letters are labeled by 1..nops(Alphabet)
MarChaList:=proc(resh)
local gu,i,N,T,Left0,Left1,Right1,mu,mu1,j,Wts:
option remember:
gu:=AlphabetList(resh):
gu:=convert(gu,list):
N:=nops(gu):
 
for i from 1 to N do
T[gu[i]]:=i:
od:
 
Left0:=LeftLettersList(resh):
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:=ListToMultiSet(FollowersList(gu[i],resh)):
 mu:=[op(mu),{seq([T[mu1[j][1]],mu1[j][2]],j=1..nops(mu1))}]:
od:
 
Wts:=[seq(Weight(gu[i]),i=1..nops(gu))]:
 
[Left1,Right1,mu,Wts]:
end:
 
#PreLeftLettersList(resh): All the possible  pre-
#letters, in the ANIMAL alphabet
#such that those with one component have width<=resh[1],
#those with two components have width<=resh[2] etc.
PreLeftLettersList:=proc(resh)
local mu,i1:
option remember:
 
mu:={}:
for i1 from 1 to nops(resh) do
mu:=mu union PreLeftLettersk(0,resh[i1]-1,i1):
od:
mu:
end:
 
#PreLeftLettersk(a,b,k): All the possible sets of `closed intervals'
#{[a1,b1],[a2,b2],...,[ak,bk]} with a<=a1<=b1<<a2<=b2<<a3..<<ak<=bk<=b
PreLeftLettersk:=proc(a,b,k)
local gu,i,mu1,gu1,j,b1:
option remember:
 
if not type(a,integer) or not type(b, integer) then
ERROR(`Bad input`):
fi:
if a>b then
RETURN({}):
fi:
 
if k=0 then
RETURN({}):
fi:
 
if  k=1 then
RETURN( {seq({[a,b1]},b1=a..b)}):
fi:
 
gu:=PreLeftLettersk(a,b-1,k):
 
for i from a to b do
mu1:=[i,b]:
gu1:=PreLeftLettersk(a,i-2,k-1):
 
for j from 1 to nops(gu1) do
gu:=gu union {gu1[j] union {mu1}}:
od:
 
od:
gu:
end: