New York Journal of Mathematics New York J. Math.

New York Journal of Mathematics

New York J. Math.7(2001) 223–231.

The Umbral Transfer-Matrix Method, III:

Counting Animals

Doron Zeilberger

Abstract. This is the third part of the five-part saga on the umbral transfer- matrix method, based on Gian-Carlo Rota’s seminal notion of the umbra.

In this article we describe the Maple package ZOO that for any specific k, automatically constructs an umbral scheme for enumerating “k-board” lattice animals (polyominoes) on the two-dimensional square lattice. Such umbral schemes enable counting these important classes of animals in polynomial time as opposed to the exponential time that is required for counting all animals.

Contents

Required reading 224

The alphabet 224

The umbral letters 225

The weight 225

Interfaces 225

Induced letters 226

Gap interfaces 226

A very important polynomial in this algorithm 227

Continuing to the left 228

An example 228

The pre-umbras 229

The pre-umbral matrix 229

The umbral matrix 229

The umbral scheme 229

A user’s manual for the maple packageZOO 230

The big disappointment 231

References 231

Received December 27, 2000. Revised November 7, 2001.

Mathematics Subject Classification. 05A15, 05A40, 82-04.

Key words and phrases. Lattice animals, polyominoes, umbral calculus, functional equations.

Supported in part by the NSF. I thank the referee for numerous corrections and improvements.

ISSN 1076-9803/01

223

Required reading

The reader is assumed to be familiar with [Z1]. It would also help to read the part of [Z0] concerned with finding generating functions for counting lattice animals with vertical cross-sections of bounded width. The present treatment is inspired by the finite case described in detail in [Z0], but with the umbral twist, getting matrices whose entries areoperatorsrather than mere polynomials, astransfer matrices.

The alphabet

Recall that asquare-lattice animal (from now onanimal) is aconnectedsubset of lattice points in the two-dimensional square lattice, up to translation-equivalence.

For example,

A:={(0,0),(0,1),(1,1),(1,2),(1,3),(0,3),(2,2)}

is (a representative) of an animal, but{(0,0),(0,1),(1,2),(1,3),(0,3)}is not, since the latter has two connected components.

We first need a convenient way to represent finite sets of integers, up to transla- tion-equivalence. If we have a ‘continuous segment’{i, i+ 1, . . . , i+j−1}, we will denote it by [j], and say that this is a 1-board set. Otherwise, we can partition the set into a union of such maximal boards, interspersed with gaps. If there are two boards (and hence one gap), we will represent this by a triple [A1, B1, A2] which represents a finite set of integers consisting ofA1 consecutive integers, followed by B1 consecutive integers thatdo notbelong to it, followed again byA2 consecutive integers that do belong to it. If the smallest member is 0 then [A1, B1, A2] is the set

{0,1,2,3, . . . , A1−1, A1+B1, A1+B1+ 1, . . . , A1+B1+A2−1}.

In general, the set of integers of type [A1, B1, A2, . . . , Bk−1, Ak] whose smallest member is 0, is the set

{0,1,2, . . . , A1−1, A1+B1, A1+B1+ 1, . . . , A1+B1+A2−1, . . . ,

A1+B1+A2+B2+· · ·+Ak−1+Bk−1, A1+B1+A2+B2+· · ·+Ak−1+Bk−1+1, . . . , A1+B1+A2+B2+· · ·+Ak−1+Bk−1+Ak−1}.

For example the set of integers {0,1,2,5,6,7,10,11,14,15,16} is represented, up to translation, by [3,2,3,2,2,2,3], and has 4 boards (of lengths 3,3,2,3) inter- spersed by 3 gaps (of lengths 2,2,2). For a k-board set of integers, we will call the k−1 gaps between the boards genuine gaps. In addition we have two ad- ditional ‘infinite gaps’, the bottom one, from −∞ to −1, and the top one, from A1+B1+A2+B2+· · ·+Ak−1+Bk−1+Ak to∞.

Each animal induces a word, that can be read from right to left, obtained by looking at the set-types induced by its vertical cross sections. For example, for the animalAabove: we first have the word

{(0,0),(0,1),(0,3)},{(1,1),(1,2),(1,3)},{(2,2)}}.

We then look at the set-types of these vertical cross-sections (ignoring the x- coordinate that is the same at any given vertical cross-section). In this example we would have [[2,1,1],[3],[1]].

So the alphabet consists of lists of positive integers, [A1, B1, A2, . . . , Bk−1, Ak], k≥1, of odd size. Such a letter-type means that at the given cross section, scanning from bottom up, we first have a board ofA1dots belonging to our animal, followed by a gap of B1 dots, followed again by a board of lengthA2, and so on, the top board being of lengthAk.

Each animal uniquely defines a word in the above alphabet. But this result- ing word is not enough to reconstruct the animal, since we also have to describe how each ‘letter’ gets interfaced to the next one. Also, for the sake of Markovity, we have to know how the k boards (of lengths A1, A2, . . . , Ak) that feature in [A1, B1, A2, . . . , Bk−1, Ak] relate to each other under the relation “reachability from the right”. This is clearly an equivalence relation, and hence thekboards of length A1, A2, . . . , Akform aset partitionamongst themselves. It is easy to see ([Z0]) that they must form anon-crossing set partition. It is well-known, and not too hard to see, that the number of non-crossing set partitions of a k-element set{1,2, . . . , k}

equals the Catalan numberCk = (2k)!/(k!(k+ 1)!). For example whenk= 1 there is obviously only one non-crossing set partition: {{1}}, whenk= 2, there are two:

{{1},{2}} and{{1,2}}; Whenk= 3, we have 5, and when k= 4 we have 14: all theB4= 15 set partitions except thecrossingset-partition{{1,3},{2,4}}.

The umbral letters

The beauty of the umbral approach is that we can consider families ofinfinitely many lettersat once. What we do is look at all the letters with the same number of boards, and inducing the same non-crossing set partition. We will call each such family an umbral letter. Thus, there is only one umbral letter for 1-board letters, namely{{1}}, there are two umbral letters for 2-board letters:{{1},{2}}, and{{1,2}}, etc. The natural classes to consider are, for a specifiedk, the setA(k), of all animals all of whose vertical cross-sections haveat mostkboards. Hence the umbral alphabet forA(k) will consist ofC1+C2+· · ·+Ck letters.

The weight

To the concrete pre-letter [A1, B1, A2, B2, . . . , Bk−1, Ak] withkboards andk−1 gaps, we assign theweight

(qx1)^A1y₁^B1(qx2)^A2y^B₂². . . y_k−1^Bk−1(qxk)^Ak.

Note that the variableqkeeps track of the number of dots, which is our main con- cern, while the variables x1, y1, x2, . . . , yk−1, xk are catalytic variables, ultimately to be all set equal to 1.

Interfaces

How can a pre-letter, let’s call itM, consisting ofmboards andm−1 gaps be placed to the left of ann-board letter,N? Let’s number the bottom (infinite) ‘gap’

(i.e. the region under the first board) ofN, by 1, the bottom board ofN by 2, the gap between the first and second boards of N, by 3, the second board by 4, and so on, until we reach the top board of N, that gets to be numbered 2n, and the infinite (last) ‘gap’ above it, that is called ‘region 2n+ 1’. Let’s call these 2n+ 1 intervals of N ‘regions’. Now we look, for each of them boards of the tentative letter where it begins and where it ends. Suppose that the first (bottom) board of

M starts at regiona1 and ends at regionb1 ofN, the second board ofM starts at regiona2and ends at regionb2 ofN,. . ., them^thboard ofM starts at regionam

and ends at regionbm. All this information is encoded into a list ofmpairs:

[[a1, b1],[a2, b2], . . . ,[am, bm]]. Of course we must havea1≤b1≤a2≤b2≤ · · · ≤am≤bm.

Not every interface is legal. We need that every component of the letter N will touch at least one board of M or else the constructed animal will die (des- tined to be disconnected). We will denote by Interfaces(m, n) the set of all the interfaces between them-boards on the left and thenboards and n+ 1 gaps (in- cluding the infinite gaps on the bottom and top). Given the letterN, the subset of Interfaces(m, n) that consists of legal continuation to the left, of the umbral letter N, will be denoted by LegalInterfaces(m, n, N). For example:

Interfaces(1,1) ={[[1,1]],[[1,2]],[[1,3]],[[2,2]],[[2,3]],[[3,3]]}, but

LegalInterfaces(1,1,{{1}}) ={[[1,2]],[[1,3]],[[2,2]],[[2,3]]}.

The interface [[1,1]] is illegal since then the first (and only) board ofM starts and ends in region 1 of N (which is the infinite bottom gap), leaving the sole board of N untouched. For a similar reason [[3,3]] is illegal, since now the only board ofM is totally immersed inside the top infinite gap.

Induced letters

Given the letterNthat stands on the right, and a legal interface of a pre-letterM withmboards, we turn the pre-letterM into a genuine letter: a non-crossing set- partition of{1,2, . . . , m}. Boardiand boardjofM belong to the same component iff they touch the same component ofN, since then it is possible to walk, from board ito boardj, without using the dots to the left ofM.

Given a letter N (a non-crossing set partition), and one of its legal interfaces, I, let’s denote by LeftLetter(I, N) the induced letterM, that the boards ofI turn into.

For example: LeftLetter([[2,3],[4,5]],{{1,3},{2}}) equals{{1},{2}}, since the first board, [2,3] touches the component{1,3}while the second board, [4,5] touches the component{2}. On the other hand LeftLetter([[2,3],[4,6]],{{1,3},{2}}) equals {{1,2}}since both boards [2,3] and [4,6] touch the same component ofN :{1,3}.

Gap interfaces

Remember from [Z1] that we need a completely algorithmic way to find the umbral evolution, i.e., starting with a generic member of a fixed k-board letter, with weight x^A₁¹y^B₁¹. . . y_k−1^Bk−1x^A_k^k, to find all the ways of continuing it. Hence we had to break it up into cases according to interfaces. But we have to break these up even further, before we are ready to compute the umbral scheme.

We need to know not only how the m boards of the left letter M interface with the letter to its right, N, but also how them+ 1 gaps do so. Here we also include the two infinite ‘gaps’: the one below the bottom board and the one above the top board. “But this is implied!” you would shout. If we have the interface [[a1, b1], . . . ,[am, bm]] of letterM in relation to letterN, which means that the first

board ofM starts at region a1 and ends at regionb1, the second board starts at regiona2and ends at regionb2, etc., then necessarily, the bottom infinite gap must go from region 1 to regiona1, the first genuine gap (between the first and second board) must go between region b1 and a2, the second gap must extend between b2 anda3 and so on. Well, there are other possibilities. For example the bottom infinite gap may end at region a1−1 (ifa1 >1). Also the gap between the first and second boards may start at region b1+ 1, or it may end in regiona2−1, or both! (if feasible), and so on.

Given an interface I, and a positive integer n, denoting the number of boards of the right letter N, we will denote by GapInterfaces(I, n) all the possible gap interfaces compatible withI. For example GapInterfaces([[1,2],[3,4]],2) equals

{[[1,1],[2,3],[4,5]],[[1,1],[2,3],[5,5]],[[1,1],[2,2],[4,5]],[[1,1],[2,2],[5,5]], [[1,1],[3,3],[4,5]],[[1,1],[3,3],[5,5]]}.

In this case the first member of each gap-interface must be [1,1], since a1 = 1.

The last gap-interface above: [[1,1],[3,3],[5,5]], together with its parent interface [[1,2],[3,4]] represents the following scenario. The letter M has two boards and three gaps. The bottom (infinite) gap extends from region 1 and ends at region 1.

The bottom board starts at region 1 and ends at region 2. The middle gap starts at region 3 and ends at region 3; the top board starts at region 3 and ends at region 4, and the infinite gap above the top board starts at region 5 and ends at region 5.

A very important polynomial in this algorithm

LetA be a symbol denoting an integer, and let z1, z2, . . . , zm be variables. We let

PA(z1, . . . , zm) =

z₁ⁱ¹z₂ⁱ²· · ·z_m^im,

where the sum extends over allm-tuples of positiveintegers (i1, . . . , im) satisfying i1+· · ·+im=A. Note thatPA(z1, . . . , zm) =z1· · ·zmhA−m(z1, . . . , zm), wherehi

is the usualcomplete homogeneous symmetric polynomialof degreei.

If Z ={z1, . . . , zm} is a set of variables, we will sometimes write the above as PA(Z), which is legitimate, since PA is a symmetric function of its arguments.

We have, of course,

PA(z1, . . . , zm) =

A−1

i=1

PA−i(z1, . . . , zm−1)zⁱ_m.

Since PA(z1) = z^A₁, we can repeatedly use the above inductive formula to get PA(z1, . . . , zm) for any m. All that is involved is summing geometric series, that Maple does very well. For example

PA(z1, z2) =z₁^Az2−z1z₂^A z1−z2 .

Note that the evaluated expression of PA(z1, . . . , zm) is a linear combination of z₁^A, z₂^A, . . . , z_m^A with coefficients that are rational functions ofz1, z2, . . . , zm.

How can each individual board and gap of the right letter be continued to the left?

So now we have the input letter with n boards, N, with its generic weight x^A₁¹y₁^B1x^A₂². . . y_n−1^Bn−1x^A_nⁿ, and we also have a specific interface and a specific gap- interface amongst its compatible ones. Let [[a1, b1],[a2, b2], . . . ,[am, bm]] be that specific interface, and let [[c1, d1],[c2, d2], . . . ,[cm+1, dm+1]] be the specific gap- interface. This means that the bottom board of N is of length A1. (Note that, e.g.,A1is symbolic, not numeric—that’s the beauty of the present approach!) Now let’s see which parts of the continued-to-the-left letter, M, reside on that bottom board. Recall that we call the first (bottom) board ofN region 2. So we look at all the intervals of the interface [[a1, b1],[a2, b2], . . . ,[am, bm]], that contain 2, i.e. all those [ai, bi] that satisfy ai ≤2 ≤bi. Whenever this is the case this means that the variablexi (that lives on thei^thboard ofM) ‘occupies space’ on the first (A1) board. Let the set of thosexi that made it beX. Similarly, we do the same for the gap-interface, with their associated variables 1 (corresponding to the infinite bot- tom gap),y1(corresponding to the gap between the bottom board to the one right above it), etc. Let the set ofy’s that thus made it be calledY. So theM-occupants of the bottom board ofN consists of the variablesX∪Y, and each of them shows up at least once. So the generating function ofallsuch possibilities isPA1(X∪Y).

Now we do the same for each of the (genuine) gaps (of lengthB1,B2, . . .) and the rest of the boards (of lengthA2, A3, . . .). Since each of the decisions of the occu- pants are independent, to get the generating function forallpossible continuations, with that specific interface and gap interface, we multiply PA1(.)PA2(.)· · ·PAn(.) times PB1(.)PB2(.)· · ·PBn−1(.), where the arguments of the PAi and PBi are the variables that “reside” on the appropriate board and gap respectively.

But, we also have to consider the bottom and top infinite gaps of the input letter N, since they also may have the boards and gaps ofM on top of them. Remember that they are called region 1 and 2n+ 1 respectively. As before we look at the appropriate variables that correspond to the boards and gaps of M that reside there, and multiply the previous product byP∞(.)P∞(.).

Finally we replace each of thexi’s (i= 1, . . . , m) byqxi, because the new boards generate more area.

An example

Suppose the (input) letter, N, on the right is the 3-board letter {{1,3},{2}}. Suppose that letter to the left (with 3 boards) has interface [[1,1],[1,3],[4,7]], and has gap-interface [[1,1],[1,1],[3,4],[7,7]].

Who intersects with the bottom infinite gap ofN? Of course the bottom infinite gap ofM, but this does not count. Then we have the first board (since 1≤1≤1), the first gap (since 1≤1≤1), and second board (since 1≤1≤3). This contributes P∞(x1, y1, x2).

Who intersects with the first (bottom) board ofN? Only the second board of M (since 1≤2≤3). This gives a contribution of PA1(x2) =x^A₂¹ to the product.

Who resides on the second gap of N, between the first and second boards of N? First x2, (since 1 ≤3 ≤3) and then y2, (since 3 ≤ 3 ≤ 4). So this gives a contribution ofPB1(x2, y2).

Who resides on the second board ofN, of lengthA2? y2(since 3≤4≤4) andx3. So this contributesPA2(y2, x3) to the product. Similarly, only x3 lives on the gap between the second and third board ofN, contributingPB2(x3). Also, onlyx3lives on the third board ofN, of lengthA3, giving a contribution ofPA3(x3), and finally, onlyx3 lives on the top infinite gap ofN, contributingP∞(x3) =x3/(1−x3).

Note that the resulting letter M is {{1},{2,3}}. So we finally multiply it by Z[{{1},{2,3}}]. Hence the pre-umbra corresponding ONLY to this particular pair of (interface, gap-interface) is

x^A₁¹y₁^B1x^A₂²y₂^B2x^A₃³Z[{{1,3},{2}}]→

P∞(qx1, y1, qx2)PA1(qx2)PB1(qx2, y2)PA2(y2, qx3)PB2(qx3)PA3(qx3)P∞(qx3)

·Z[{{1},{2,3}}].

The pre-umbras

Now we (or rather our computers) do this for each and every one of the inter- faces and each and every one of its accompanying gap-interfaces, and add all these expressions up. This will give us the action of our umbral scheme on a generic monomialx^A₁¹y^B₁¹x^A₂²y₂^B2x^A₃³Z[{{1,3},{2}}]. That’s what we called pre-umbra in [Z1].

The pre-umbral matrix

Now we form a square matrix whose dimension is the size of the animal alphabet (i.e. C1+C2+· · ·+Ck), both of whose rows and columns are labelled by letters (non-crossing partitions of sets of ≤kelements). The entry corresponding to the row labelled by L1 and column labelled by L2 is the coefficient of Z[L2] in the pre-umbra constructed above, which is our umbra applied to the generic monomial x^A₁¹y₁^B1x^A₂². . . y_m−1^Bm−1x^A_m^mZ[L1], wheremis the number of boards ofL1.

The umbral matrix

We now convert, as described in [Z1], each of the entries of the pre-umbral matrix into a full-fledged umbra. (this is accomplished by procedureToUmbrainROTA, that has been transported toZOO).

The umbral scheme

Recall that ([Z1]) in addition to the umbral matrix, an umbral scheme also needs a subset ofstarting letters, ending letters, and the initial generating functions for the starting letters. Since the letters correspond to the (necessarily non-crossing) set partitions of the set of boards, and two boards belong to the same member-set of the set-partition iff they can be reached from each other by only using pointsto the right, and we go (as in Arabic) from right to left, the rightmost (first) letter can only be the one corresponding to all singletons. Hence there arekright-letters altogether: {{1}},{{1},{2}}, . . .{{1},{2}, . . . ,{k}}. Who are the terminal letters?

Here we have the other extreme, since the boards may not reach each other from the left (since they are leftmost), and since animals are connected, all the boards must belong to the same component, and the only eligible set-partitions are those

consisting ofonemember set, namelyeverything. So the terminal (leftmost) letters are : {{1}},{{1,2}}, . . .{{1,2, . . . , k}}.

Finally the initial generating function for one-letter (pre-) animals, for the i- board letter (1≤i≤k),{{1},{2}, . . . ,{i}}, is obviously

i j=1

qxj

1−qxj i−1

j=1

yj

1−yj,

since the initialiboards and initiali−1 gaps between them may be of any positive length independent of each other.

A user’s manual for the maple package ZOO

We strongly advise the reader to study carefully the source code of the Maple package ZOO that automatically finds umbral schemes for ≤ k-board animals for arbitrary k. It does not require ROTA, since all the necessary procedures of the latter were transported.

The main procedures ofZOOareAniUmScandApplyUmSc. If you want to get the umbral scheme for enumerating animals with ≤ k boards in each vertical cross- section, type AUSk:=AniUmSc(k,x,y,q);. Here k is a specific positive integer (k=1,2, . . .), while x and y are the indexed variable-names for the board- and gap-lengths as described above, and q is the variable of interest, that carries the number of dots.

Once Maple gives you the umbral scheme (that we chose to callAUSkabove), to get the firstnterms in the enumerating series (what physicists call “series expan- sions”) type ApplyUmSc(AUSk,q,n,var):, where var is the set of catalytic vari- ables: {x[1], y[1], x[2], . . . y[k−1], x[k]}. E.g., tryApplyUmSc(AUS1,q,n,{x[1]}):

andApplyUmSc(AUS2,q,n,{x[1],y[1],x[2]}): .

Since outputting the umbral scheme,AUS2, for≤2-board animals takes a while, we pre-computedAUS2, and for the sake of completeness, alsoAUS1.

TypingApplyUmSc(AUS2,q,54,{x[1],y[1],x[2]}): and waiting for a few days, extends sequenceA001170(FormerlyM1638andN0640) (“Board-pair-pile poly- ominoes with n cells”, first computed in [L]) of Neil Sloane and Simon Plouffe’s Encyclopediaanddatabaseto 54 terms. You would get:

[1, 2, 6, 19, 63, 216, 760, 2723, 9880, 36168, 133237, 492993, 1829670, 6804267, 25336611, 94416842, 351989967, 1312471879, 4894023222, 18248301701, 68036380665, 253638655582, 945464013411, 3523978989671, 13133649924269, 48944841261703, 182390886053785, 679639952406737, 2532435605836553, 9435940029787771,

35157829654829347, 130993992060546335, 488061959593417980, 1818420122974985383, 6775015368226385755, 25242011759461486461, 94045041136136802213,

350385854676874166894, 1305438172166371546918, 4863684396241586531678, 18120658979728427379998, 67512198042235076760287, 251530274898487735498572, 937126264995917017697537, 3491450036706654367545738, 13008087968822268294707203, 48464198629752538664862046, 180562916626733292681832702, 672722655136932068675036320, 2506360408024259482601919315, 9337937683903257909568706940,

34790318720202928318378465769, 129618154246548101581553316346, 482917840548933948578460002791].

The big disappointment

ZOO can, in principle, find an umbral scheme for any given, fixed, number of boards. But the number of interfaces grows so fast that Maple ran out of memory even when our computer tried to compute the umbral scheme for 3-board animals, i.e., it refused to perform the command: AUS3:=AniUmSc(3,x,y,q);.

We are almost sure that with a more careful implementation, and/or by trans- porting to numeric programming languages such asC, AUS3:=AniUmSc(3,x,y,q);

is still feasible, but frankly, we doubt whether it is worth the effort.

The most important point is that there exists a program that can generate (at least in principle) a polynomial-time (in n), scheme for enumerating k-board animals with ≤ n cells, for any fixed given k. So what if the ‘polynomial’ is so big as to make it impractical? I will be very impressed if you can justprove the existenceof anO(n1000000000000000) algorithm forSatisfiability!

Many Thanks are due to the dedicated referee for his or her very careful reading, that corrected many minor errors.

References

[L] W. F. Lunnon,Counting polyominoes, Computers in Number Theory (A. O. L. Atkin and B. J. Birch, eds.), Academic Press, NY, 1971, pp. 347-372, Zbl 0214.51604.

[Z0] Doron Zeilberger, Symbol-crunching with the transfer-matrix method in order to count skinny physical creatures, Integers (http://www.integers-ejcnt.org)0 (2000), paper A9 (34 pages), MR 2001e:05010, Zbl 0954.82006.

[Z1] Doron Zeilberger,The umbral transfer-matrix method. I. Foundations, J. Comb. Theory Ser.

A91(2000), 451–463, MR 2001g:05018, Zbl 0961.05003.

[Z2] Doron Zeilberger, The umbral transfer-matrix method. II. Counting plane partitions, Per- sonal Journal of Ekhad and Zeilberger,http://www.math.rutgers.edu/~zeilberg/pj.html.

[Z4] Doron Zeilberger,The umbral transfer-matrix method. IV. Counting self-avoiding polygons and walks, Elec. J. Comb.8(1) (2001), R28 (17 pages).

[Z5] Doron Zeilberger, The umbral transfer-matrix method. V. The Goulden-Jackson cluster method for infinitely many mistakes, submitted. Available from the author’s website.

Department of Mathematics, Rutgers University (New Brunswick), Hill Center- Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA

[email protected] http://www.math.rutgers.edu/˜zeilberg/

This paper is available via http://nyjm.albany.edu:8000/j/2001/7-14.html.