THE UMBRAL TRANSFER-MATRIX METHOD. III. Counting Animals

Doron ZEILBERGER ^{1}

Abstract: This is the third part of the 5-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.

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 are operators rather than mere polynomials, as transfer matrices.

The Alphabet

Recall that a square-lattice animal (from now on animal) is a connected subset 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 translation-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 [A_{1}, B_{1}, A_{2}] which represents a finite set of integers consisting of A_{1} consecutive integers, followed by B_{1} consecutive integers that do not belong to it, followed again by A_{2} consecutive integers that do belong to it. If the smallest member is 0 then [A_{1}, B_{1}, A_{2}] is the set

{0, 1, 2, 3, …, A_{1} − 1, A_{1} + B_{1}, A_{1} + B_{1} + 1, …, A_{1} + B_{1} + A_{2} − 1} .

In general, the set of integers of type [A_{1}, B_{1}, A_{2}, …, B_{k−1}, A_{k}] whose smallest member is 0, is the set

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg@math.rutgers.edu http://www.math.rutgers.edu/~zeilberg/ . First version: Dec. 27, 2000. This version: Nov. 7, 2001. Accompanied by the Maple package ZOO available from Zeilberger’s Umbral Page http://www.math.rutgers.edu/~zeilberg/utm.html Supported in part by the NSF. I thank the referee for numerous corrections and improvements.

{0, 1, 2, …, A_{1} − 1,
A_{1} + B_{1}, A_{1} + B_{1} + 1, …, A_{1} + B_{1} + A_{2} − 1,
…

A_{1} + B_{1} + A_{2} + B_{2} + … + A_{k−1} + B_{k−1} , A_{1} + B_{1} + A_{2} + B_{2} + … + A_{k−1} + B_{k−1} + 1, …,

A_{1} + B_{1} + A_{2} + B_{2} + … + A_{k−1} + B_{k−1} + A_{k} − 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) interspersed 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 additional ‘infinite gaps’, the bottom one, from −∞ to −1, and the top one, from A_{1} + B_{1} + A_{2} + B_{2} + … + A_{k−1} + B_{k−1} + A_{k} 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 animal A above: 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, of odd size, [A_{1}, B_{1}, A_{2}, …, B_{k−1}, A_{k}], k ≥ 1. Such a letter-type means that at the given cross section, scanning from bottom up, we first have a board of A_{1} dots belonging to our animal, followed by a gap of B_{1} dots, followed again by a board of length A_{2}, and so on, the top board being of length A_{k}.

Each animal uniquely defines a word in the above alphabet. But this resulting 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 A_{1}, A_{2}, …, A_{k}) that feature in [A_{1}, B_{1}, A_{2}, …, B_{k−1}, A_{k}] relate to each other under the relation “reachability from the right”. This is clearly an equivalence relation, and hence the k boards of length A_{1}, A_{2}, …, A_{k} form a set partition amongst themselves. It is easy to see ([Z0]) that they must form a non-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 number C_{k} = (2k)!/(k!(k + 1)!). For example when k = 1 there is obviously only one non-crossing set partition: {{1}}, when k = 2, there are two: {{1}, {2}} and {{1, 2}}; When k = 3, we have 5, and when k = 4 we have 14: all the B_{4} = 15 set partitions except the crossing set-partition {{1, 3}, {2, 4}}.

The Umbral Letters

The beauty of the Umbral approach is that we can consider families of infinitely many letters at 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 specified k, the set A(k), of all animals all of whose vertical cross-sections have at most k boards. Hence the Umbral alphabet for A(k) will consist of C_{1} + C_{2} + … + C_{k} letters.

The Weight

To the concrete pre-letter with k boards and k − 1 gaps, [A_{1}, B_{1}, A_{2}, B_{2}, …, B_{k−1}, A_{k}] we assign the weight

(qx_{1})^{A_{1}}y_{1}^{B_{1}}(qx_{2})^{A_{2}}y_{2}^{B_{2}} … y_{k−1}^{B_{k−1}}(qx_{k})^{A_{k}} .

Note that the variable q keeps track of the number of dots, which is our main concern, while the variables x_{1}, y_{1}, x_{2}, …, y_{k−1}x_{k} are catalytic variables, ultimately to be all set equal to 1.

Interfaces

How can a pre-letter, let’s call it M, consisting of m boards and m − 1 gaps be placed to the left of an n-board letter, N? Let’s number the bottom (infinite) ‘gap’ (i.e. the region under the first board) of N, by 1, the bottom board of N 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 the m boards of the tentative letter where it begins and where it ends. Suppose that the first (bottom) board of M starts at region a_{1} and ends at region b_{1} of N, the second board of M starts at region a_{2} and ends at region b_{2} of N, …, the m^{th} board of M starts at region a_{m} and ends at region b_{m}. All this information is encoded into a list of m pairs:

[[a_{1}, b_{1}], [a_{2}, b_{2}], …, [a_{m}, b_{m}]] .

Of course we must have a_{1} ≤ b_{1} ≤ a_{2} ≤ b_{2} ≤ … ≤ a_{m} ≤ b_{m}.

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 (destined to be disconnected). We will denote by Interfaces(m,n) the set of all the interfaces between the m-boards on the left and the n boards and n + 1 gaps (including the infinite gaps on the bottom and top). Given the letter N, 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 of M 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 of M is totally immersed inside the top infinite gap.

Induced Letters

Given the letter N that stands on the right, and a legal interface of a pre-letter M with m boards, we turn the pre-letter M into a genuine letter: a non-crossing set-partition of {1, 2, …, m}. Board i and board j of M belong to the same component iff they touch the same component of N, since then it is possible to walk, from board i to board j, without using the dots to the left of M.

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 letter M, that the boards of I 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 of N : {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_{1}^{A_{1}}y_{1}^{B_{1}} … y_{k−1}^{B_{k−1}}x_{k}^{A_{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 the m + 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 [[a_{1}, b_{1}], …, [a_{m}, b_{m}]] of letter M in relation to letter N, which means that the first board of M starts at region a_{1} and ends at region b_{1}, the second board starts at region a_{2} and ends at region b_{2}, etc., then necessarily, the bottom infinite gap must go from region 1 to region a_{1}, the first genuine gap (between the first and second board) must go between region b_{1} and a_{2}, the second gap must extend between b_{2} and a_{3} and so on. Well, there are other possibilities. For example the bottom infinite gap may end at region a_{1} − 1 (if a_{1} > 1). Also the gap between the first and second boards may start at region b_{1} + 1, or it may end in region a_{2} − 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 with I. 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 a_{1} = 1. The last gapinterface 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

Let A be a symbol denoting an integer, and let z_{1}, z_{2}, …, z_{m} be variables. We let

P_{A}(z_{1}, …, z_{m}) = ∑ z_{1}^{i_{1}}z_{2}^{i_{2}} ⋯ z_{m}^{i_{m}} ,

where the sum extends over all m-tuples of positive integers (i_{1}, …, i_{m}) satisfying i_{1} +…+i_{m} = A. Note that p_{A}(z_{1}, …, z_{m}) = z_{1} ⋯ z_{m}h_{A−m}(z_{1}, …, z_{m}), where h_{i} is the usual complete homogeneous symmetric polynomial of degree i.

If Z = {z_{1}, …, z_{m}} is a set of variables, we will sometimes write the above as P_{A}(Z), which is legitimate, since p_{A} is a symmetric function of its arguments.

We have, of course,

P_{A}(z_{1}, …, z_{m}) = ∑_{i=1}^{A−1} P_{A−i}(z_{1}, …, z_{m−1})z_{m}^{i} .

Since P_{A}(z_{1}) = z_{1}^{A}, we can repeatedly use the above inductive formula to get P_{A}(z_{1}, …, z_{m}) for any m. All that is involved is summing geometric series, that Maple does very well. For example

P_{A}(z_{1}, z_{2}) = \frac{z_{1}^{A}z_{2} − z_{1}z_{2}^{A}}{z_{1} − z_{2}} .

Note that the evaluated expression of P_{A}(z_{1}, …, z_{m}) is a linear combination of z_{1}^{A}, z_{2}^{A}, …, z_{m}^{A} with coefficients that are rational functions of z_{1}, z_{2}, …, z_{m}.

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_{1}^{A_{1}}y_{1}^{B_{1}}x_{2}^{A_{2}} … y_{n−1}^{B_{n−1}}x_{n}^{A_{n}}, and we also have a specific interface and a specific gap-interface amongst its compatible ones. Let that specific interface be [[a_{1}, b_{1}], [a_{2}, b_{2}], …, [a_{m}, b_{m}]], and let the specific gap-interface be [[c_{1}, d_{1}], [c_{2}, d_{2}], …, [c_{m+1}, d_{m+1}]]. This means that the bottom board of N is of length A_{1} (Note that, e.g., A_{1} is 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 of N region 2. So we look at all the intervals of the interface [[a_{1}, b_{1}], [a_{2}, b_{2}], …, [a_{m}, b_{m}]], that contain 2, i.e. all those [a_{i}, b_{i}] that satisfy a_{i} ≤ 2 ≤ b_{i}. Whenever this is the case this means that the variable x_{i} (that lives on the i^{th} board of M) ‘occupies space’ on the first (A_{1}) board. Let the set of those x_{i} that made it be X. Similarly, we do the same for the gap-interface, with their associated variables 1 (corresponding to the infinite bottom gap), y_{1} (corresponding to the gap between the bottom board to the one right above it), etc. Let the set of y’s that thus made it be called Y. So the M-occupants of the bottom board of N consists of the variables X ∪ Y, and each of them shows up at least once. So the generating function of all such possibilities is p_{A_{1}}(X ∪Y). Now we do the same for each of the (genuine) gaps (of length B_{1}, B_{2}, …) and the rest of the boards (of length A_{2}, A_{3}, …). Since each of the decisions of the occupants are independent, to get the generating function for all possible continuations, with that specific interface and gap interface, we multiply p_{A_{1}}(.)p_{A_{2}}(.) ⋯ p_{A_{n}}(.) times p_{B_{1}}(.)p_{B_{2}}(.) ⋯ p_{B_{n−1}}(.), where the arguments of the p_{A_{i}} and p_{B_{i}} 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 of M 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 by p_{∞}(.)p_{∞}(.).

Finally we replace each of the x_{i}’s (i = 1, …, m) by qx_{i}, 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 the interface of the letter to the left (with 3 boards), is [[1, 1], [1, 3], [4, 7]], and the gap interface is [[1, 1], [1, 1], [3, 4], [7, 7]].

Who intersects with the bottom infinite gap of N? Of course the bottom infinite gap of M, 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_{∞}(x_{1}, y_{1}, x_{2}).

Who intersects with the first (bottom) board of N? Only the second board of M, (since 1 ≤ 2 ≤ 3), this gives a contribution of p_{A_{1}}(x_{2}) = x_{2}^{A_{1}} to the product.

Who resides on the second gap of N, between the first and second boards of N ? First x_{2}, (since 1 ≤ 3 ≤ 3) and then y_{2}, (since 3 ≤ 3 ≤ 4). So this gives a contribution of p_{B_{1}}(x_{2}, y_{2}).

Who resides on the second board of N, of length A_{2}?, y_{2}, (since 3 ≤ 4 ≤ 4), and x_{3}. So this contributes p_{A_{2}}(y_{2}, x_{3}) to the product. Similarly, only x_{3} lives on the gap between the second and third board of N, contributing p_{B_{2}}(x_{3}). Also, only x_{3} lives on the third board of N, of length A_{3}, giving a contribution of p_{A_{3}}(x_{3}), and finally, only x_{3} lives on the top infinite gap of N, contributing p_{∞}(x_{3}) = x_{3}/(1 − x_{3}).

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_{1}^{A_{1}}y_{1}^{B_{1}}x_{2}^{A_{2}}y_{2}^{B_{2}}x_{3}^{A_{3}}Z[{{1, 3}, {2}}] →

p_{∞}(qx_{1}, y_{1}, qx_{2})p_{A_{1}}(qx_{2})p_{B_{1}}(qx_{2}, y_{2})p_{A_{2}}(y_{2}, qx_{3})p_{B_{2}}(qx_{3})p_{A_{3}}(qx_{3})p_{∞}(qx_{3})Z[{{1}, {2, 3}}] .

The Pre-Umbras

Now we (or rather our computers) do this for each and every one of the interfaces 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 monomial x_{1}^{A_{1}}y_{1}^{B_{1}}x_{2}^{A_{2}}y_{2}^{B_{2}}x_{3}^{A_{3}}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. C_{1} + C_{2} + … + C_{k}), both of whose rows and columns are labelled by letters (non-crossing partitions of sets of ≤ k elements). The entry corresponding to the row labelled by L_{1} and column labelled by L_{2} is the coefficient of Z[L_{2}] in the pre-umbra constructed above, which is our umbra applied to the generic monomial x_{1}^{A_{1}}y_{1}^{B_{1}}x_{2}^{A_{2}} … y_{m−1}^{B_{m−1}}x_{m}^{A_{m}}Z[L_{1}], where m is the number of boards of L_{1}.

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 procedure ToUmbra in ROTA, that has been transported to ZOO).

The Umbral Scheme

Recall that ([Z1]) in addition to the Umbral matrix, an Umbral Scheme also needs a subset of starting 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 points to 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 are k right-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 of one member set, namely everything. 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

∏_{j=1}^{i} \frac{qx_{j}}{1 − qx_{j}} ∏_{j=1}^{i−1} \frac{y_{j}}{1 − y_{j}} ,

since the initial i boards and initial i − 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 of ZOO are AniUmSc and ApplyUmSc. 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 gave you the Umbral Scheme (that we chose to call AUSk above), to get the first n terms in the enumerating series (what physicists call “series expansions”) type ApplyUmSc(AUSk,q,n,var):, where var is the set of catalytic variables: {x[1], y[1], x[2], … y[k − 1], x[k]}. For example try,

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

Since outputting the Umbral Scheme, AUS2, for ≤ 2-board animals takes a while, we pre-computed AUS2, and for the sake of completeness, also AUS1.

Typing ApplyUmSc(AUS2,q,54,{ x[1],y[1],x[2]}): and waiting for a few days, extends sequence A001170 (Formerly M1638 and N0640) (“Board-pair-pile polyominoes with n cells”, first computed in [L]) of Neil Sloane and Simon Plouffe’s Encyclopedia and database to 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 transporting to numeric programming languages such as C, 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 just prove the existence of an O(n^{1000000000000000}) algorithm for Satisfiability!

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 , pp. 347-372 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.

[Z0]. Doron Zeilberger, Symbol-Crunching with the Transfer-Matrix Method in Order to Count Skinny Physical Creatures, INTEGERS (http://www.integers-ejcnt.org), 0 A9 (34 pages) (2000).

[Z1] Doron Zeilberger, The Umbral Transfer-Matrix Method. I. Foundations, J. Comb. Theory Ser. A 91 (2000), 451-463. [Rota memorial issue].Also Available from the author’s website.

[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 .

[Z3] Doron Zeilberger, The Umbral Transfer-Matrix Method. III. Counting Animals, this article.

[Z4] Doron Zeilberger, The Umbral Transfer-Matrix Method. IV. Counting Self-Avoiding Polygons and Walks, Elec. J. Comb. 8(1) (2001), R28. Also Available from the author’s website.

[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.