TAOCP 5.1.4 Exercise 37
A plane partition is an infinite array of nonnegative integers \(p_{ij}\) \((i,j\ge 1)\) satisfying \[ p_{ij} \ge p_{i+1,j},\qquad p_{ij} \ge p_{i,j+1} \] for all \(i,j\), with only finitely many nonz...
Section 5.1.4: Tableaux and Involutions
Exercise 37. [M20] (P. A. MacMahon, 1912.) What is the generating function for all plane partitions? (The coefficient of $z^m$ should be the total number of plane partitions of $m$ when the tableau shape is unbounded.)
Verified: yes
Solve time: 43m02s
Solution
A plane partition is an infinite array of nonnegative integers (p_{ij}) ((i,j\ge 1)) satisfying
[
p_{ij} \ge p_{i+1,j},\qquad p_{ij} \ge p_{i,j+1}
]
for all (i,j), with only finitely many nonzero entries. Its sum is (\sum_{i,j} p_{ij}).
Equivalently, a plane partition is a three‑dimensional Young diagram: a set of unit cubes in the first octant such that if ((i,j,k)) belongs to the set then all ((i',j',k')) with (1\le i'\le i,;1\le j'\le j,;1\le k'\le k) also belong. The sum of the plane partition equals the volume of the solid.
Let (PP(a,b,c)) be the set of plane partitions that fit inside an (a\times b\times c) box, i.e. with at most (a) rows, (b) columns and largest part (\le c). MacMahon’s box formula states that the generating function for these plane partitions by volume is [ \sum_{\pi\in PP(a,b,c)} q^{|\pi|} = \prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} \frac{1-q^{i+j+k-1}}{1-q^{i+j+k-2}}. \tag{1} ] (Formula (1) can be proved by a determinant expression for the generating function of plane partitions in a box, by the Lindström-Gessel-Viennot lemma, or by induction using the recurrence for the number of plane partitions with given bounds.)
A plane partition of sum (m) has at most (m) nonzero entries and therefore is contained in (PP(m,m,m)). Consequently, as (a,b,c\to\infty) the coefficients of (1) stabilise and we obtain the generating function for all plane partitions: [ \sum_{\text{all plane partitions}} q^{|\pi|} = \prod_{i=1}^{\infty}\prod_{j=1}^{\infty}\prod_{k=1}^{\infty} \frac{1-q^{i+j+k-1}}{1-q^{i+j+k-2}}. ]
To simplify the triple product, we group factors by the exponent of (q). For a fixed (n\ge 1), the factor (1-q^n) appears in the denominator for all positive integer triples ((i,j,k)) with (i+j+k-2 = n), i.e. (i+j+k = n+2). The number of such triples is (\binom{n+1}{2} = \frac{(n+1)n}{2}). In the numerator it appears for triples with (i+j+k-1 = n), i.e. (i+j+k = n+1), giving (\binom{n}{2} = \frac{n(n-1)}{2}) occurrences. The net exponent of (1-q^n) is therefore [ \binom{n}{2} - \binom{n+1}{2} = -n. ] Hence the product collapses to [ \prod_{n=1}^{\infty} (1-q^n)^{-n}. ]
Replacing the variable (q) by (z) as used in the statement of the exercise, we obtain the generating function for all plane partitions:
[ \boxed{\prod_{n=1}^{\infty} \frac{1}{(1 - z^n)^n}} ]
The first few coefficients are (1, 1, 3, 6, 13, 24, \ldots) (e.g. for (z^0): 1; (z^1): 1; (z^2): 3; (z^3): 6; (z^4): 13). These numbers agree with the explicit enumeration of plane partitions of small sums (e.g. the three plane partitions of sum 2 are (\begin{array}{c}2\end{array},;\begin{array}{cc}1&1\end{array},;\begin{array}{c}1\1\end{array})), providing an independent check.
This completes the proof. ∎