THE UMBRAL TRANSFER-MATRIX METHOD: II. Counting Plane Partitions

Doron ZEILBERGER ^{1}

Abstract: We continue 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 PPar that automatically constructs Umbral Schemes for enumerating r-rowed plane partitions, for specific but arbitrary r, and that also automatically constructs Evolution Umbra for monotone triangles.

An Umbra for r-rowed plane partitions

Recall that an r × k plane-partition is a matrix of non-negative integers (a_{i,j}), 1 ≤ i ≤ r, 1 ≤ j ≤ k, that is weakly decreasing along every row and every column. There is only one ‘state’ i.e. vertextype, and it is parameterized by non-increasing tuples of non-negative integers: (a_{1}, …, a_{r}), where a_{1} ≥ a_{2} ≥ … ≥ a_{r} ≥ 0. The Rota operator connecting one column to the next is the operator sending a generic monomial x_{1}^{b_{1}}x_{2}^{b_{2}} ⋯ x_{r}^{b_{r}} corresponding to the current leftmost column, to the sum of all monomials (qx_{1})^{a_{1}}(qx_{2})^{a_{2}} ⋯ (qx_{r})^{a_{r}} , where the sum ranges over all a_{1} ≥ a_{2} ≥ … ≥ a_{r} ≥ 0 for which a_{i} ≥ b_{i} for all i between 1 and r.

In order to do this automatically, we have to partition the summed set into ‘chambers’. For any given i (1 ≤ i ≤ r), of course it is required that a_{i} ≥ b_{i}, i.e. thinking of the b_{1}, b_{2}, …, b_{r} as the heights of girls who stand in (weakly) decreasing order, and who each must find a (weakly) taller boy as her dancing partner, and the chosen boys must also be in (weakly) decreasing order, then a short girl is allowed to pick a boy that is even taller than her taller neighbor, in fact, the shortest girl may even pick a boy that is taller than the tallest girl. BUT, if she does that, then of course all the other boys must be taller than the tallest girl.

So for a fixed (b_{1}, …, b_{r}), and a legal choice (a_{1}, …, a_{r}), let’s call the profile f(i) the smallest j such that a_{i} ≥ b_{j}. Of course f(i) ≤ i, and f(1) ≤ f(2) ≤ … ≤ f(r). It is well known and easy to see that there are C_{r} = \binom{2r}{r}/(r + 1) such sequences, and they are sometimes called Catalan sequences. For example when r = 2 there are 2 Catalan sequences: 11 and 12, and when r = 3 there are 5: 111, 112, 113, 122, 123.

Now for any specific profile, f, it is easy to sum (qx_{1})^{a_{1}}(qx_{2})^{a_{2}} ⋯ (qx_{r})^{a_{r}} , over all (a_{1}, …, a_{r}) with that profile, since it only involves summing series of the form

P_{m}(A, B; z) := ∑_{A≤i_{1}≤i_{2}≤...≤i_{m}≤B} z_{1}^{i_{1}} … z_{m}^{i_{m}} ,

that Maple (and even you!) can evaluate in closed form (symbolically). Then the required sum is a product of a certain number of such expressions, where the number of terms in the product equals the cardinality of the range of f. For example the profile 1111 would only have P_{4}(b_{1}, ∞; qx_{1}, qx_{2}, qx_{3}, qx_{4}) while the profile 1234 would be

1 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. zeilberg@math.temple.edu

http://www.math.temple.edu/~zeilberg/ . Oct. 25, 2000. Exclusive to The Personal Journal of Ekhad and Zeilberger http://www.math.temple.edu/~zeilberg/pj.html . Accompanied by Maple package PPar available from Zeilberger’s Umbral Page http://www.math.temple.edu/~zeilberg/umb.html . Supported in part by the NSF.

P_{1}(b_{1}, ∞; qx_{1})P_{1}(b_{2}, b_{1} − 1; qx_{2})P_{1}(b_{3}, b_{2} − 1; qx_{3})P_{1}(b_{4}, b_{3} − 1; qx_{4}) .

For details study carefully the source code of the Maple package PPar.

The next step is to find the pre-umbra by summing all these C_{r} expressions, and finally the master package ROTA converts the pre-umbra to a full-fledged Umbral Scheme. The function call is UmbralScPP(x,q,t,r). Here x is the indexed variable, as above, q is the usual q that keeps track of the sum of the parts of the plane-partition, and t keeps track of the number of columns. Note that the zero vector is permitted, so the coeff. of t^{k} is really the generating function for plane partition with at most k columns and at most r rows, i.e. those whose 3D Ferrers diagram fit in an r ×k ×∞ box, and in addition it is weighted by x_{1}^{a_{1}} … x_{r}^{a_{r}}, where a_{1}, …, a_{r} is the leftmost column. For example, to get (essentially) the umbra derived by hand in [Z1] (for 2-rowed plane-partitions)

type: UmbralScPP(x,q,t,2).

To get the generating function for n-rowed, r-column plane partitions, using the variable q, type GFPP(n,r,q);, for specific r and n. For example try GFPP(2,3,q);. Of course, we already have MacMahon’s box theorem, so we don’t need PPar, but the point is to illustrate a general method that could be applied in many other situations, where closed form, or even efficient algorithms, are not known and may not exist. In fact CheckPercy(n,r,q); compares the answer to MacMahon’s box theorem, and returns true if it agrees. If you want to keep track of the leftmost column, i.e. the weight is the previous one times x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{n}^{a_{n}}, where a_{1}, …, a_{n} are the entries of the leftmost row, then type: GFPPx(n,x,r,q); . Here n and r are specific integers, while x and q are symbols.

For example, GFPPx(3,x,2,q);.

An Umbra for Monotone Triangles

Recall that a monotone triangle (a.k.a. strict Gelfand pattern) of size n is a triangular array of positive integers (a_{i,j}), n ≥ i ≥ j ≥ 1, such that a_{i,j} < a_{i,j+1} and a_{i−1,j−1} ≤ a_{i,j} ≤ a_{i−1,j}. The monotone triangles of size n whose bottom row is 1, 2, …, n, i.e. for which a_{n,j} = j for j = 1, …, n, are in simple bijection with n × n alternating sign matrices.

I believe that the Umbral Transfer Matrix method could be used to get yet another proof of the Alternating Sign Matrix Conjecture (see [B] for a gripping account). But it is not clear that this would be easier than the two already existing proofs. Since I have already paid my dues working on this problem, I will leave this as a challenge to the reader. Here I will only use it as an illustrative example, and describe the automatic generation of the generating function for all monotone triangles, but of a specific size. Then extracting the coefficient of x_{1}x_{2}^{2}x_{3}^{3} … x_{n}^{n} would give the n-th term in the famous ASM sequence.

Suppose that the bottom row is now (b_{1}, …, b_{k}). The weight of such a monotone triangle is x_{1}^{b_{1}} ⋯ x_{k}^{b_{k}}. Which tuples (a_{1}, …, a_{k+1}) may continue it to the (k + 1)-th row? We need to sum x_{1}^{a_{1}} ⋯ x_{k+1}^{a_{k+1}} over all legal (k + 1)-tuples such that a_{1} < a_{2} < … < a_{k} < a_{k+1} and a_{1} ≤ b_{1} ≤ a_{2} ≤ … ≤ b_{k} ≤ a_{k+1}. The summed-over set can be partitioned into 2^{k} subsets, according to profile. The profile of (a_{1}, …, a_{k+1}) is the subset of {1, 2, … k} such that b_{i} = a_{i+1}. It is easy to explicitly (symbolically) sum the monomials corresponding to tuples belonging to any one profile. PPar does that for each of the 2^{k} profiles, getting expressions in x_{1}, …, x_{k+1} and b_{1}, …, b_{k}. It adds them all up thereby getting the preumbra connecting a generic monomial x_{1}^{b_{1}} ⋯ x_{k}^{b_{k}} to the sum of all its legal extensions. Then procedure ToUmbra from the master package ROTA turns the pre-umbra into the Umbra T_{k} connecting monotone triangles of size k to those of size k + 1. This is done with procedure UmbraMT of PPar. The function call is UmbraMT(x,k);,where x is the symbol for the indexed variable, and k is a specific integer. For example try UmbraMT(x,3);. To get the generating function for monotone triangles of size k (which is just T_{k−1}T_{k−2} … T_{1}(x_{1})), type GFMT(x,k);. To get the number of monotone triangles of size k with a prescribed bottom row (a list of increasing integers), type MT(bottom row);. For example MT([1,2,3,4,5]); should yield the number of 5×5 alternating sign matrices (429), while MT([1,3,5,7]); gives the number of monotone triangles of size 4 whose bottom row is 1, 3, 5, 7. Once again, note that this is not the most efficient way to crank out numbers, and the main justification of procedure MT is to test the validity of the program.

Other Symmetry Classes and Solid Partitions

The Same approach should enable one to construct umbra, or Umbral Schemes, for symmetric, totally symmetric, and other kinds of plane partitions. It should also be amenable to counting solid partitions, and more generally, generalized partitions that live on a poset, taking Stanley’s classical theory of P-partitions ([S]) as a starting point, and building Umbral Schemes on it.

REFERENCES

[B] David Bressoud, “Proofs and Confirmations: The Story of The Alternating Sign Matrix Conjecture”, Cambridge University Press and The Math. Assoc. of Amer., 1999.

[S] Richard P. Stanley, “Enumerative Combinatorics”, volume 1, Wadsworth, Monterey, California, 1986. Reprinted by Cambridge University Press.

[Z1] Doron Zeilberger, The Umbral Transfer-Matrix Method: I. Foundations, J. Comb. Theory Ser. A 91 (2000), 451-463. [Rota memorial issue].

[Z2] Doron Zeilberger, The Umbral Transfer-Matrix Method: II. Counting Plane Partitions, Personal Journal of Ekhad and Zeilberger, http://www.math.temple.edu/~zeilberg/pj.html . (this article).

[Z3] Doron Zeilberger, The Umbral Transfer-Matrix Method: III. Counting Animals, in preparation.

[Z4] Doron Zeilberger, The Umbral Transfer-Matrix Method: IV. Counting Self-Avoiding Polygons and Walks, in preparation.

[Z5] Doron Zeilberger, The Umbral Transfer-Matrix Method: V. The Goulden-Jackson Cluster-Method for Infinitely Many Mistakes, in preparation.