40.03.07 · combinatorics / symmetric-functions-rsk

Plane Partitions and the MacMahon Box Formula

shipped3 tiersLean: none

Anchor (Master): Stanley 1999 *Enumerative Combinatorics, Volume 2* 2e (Cambridge) §7.20-7.22, Appendix (plane partitions and their symmetry classes, the box formula by RSK and by nonintersecting lattice paths, the Hillman-Grassl correspondence and the trace generating function); Macdonald 1995 *Symmetric Functions and Hall Polynomials* 2e (Oxford) Ch. I §5 Ex. (the box formula as a principal specialisation of the Cauchy identity); Bressoud 1999 *Proofs and Confirmations* (Cambridge / MAA) (the ten symmetry classes and the Andrews-Macdonald-Mills-Robbins-Rumsey enumerations, the ASM theorem of Zeilberger); MacMahon 1916 *Combinatory Analysis* (Cambridge); Cohn-Larsen-Propp 1998 *New York J. Math.* 4 (the arctic-circle and limit-shape phenomenon for boxed plane partitions)

Intuition Beginner

Imagine pouring sand into the corner of a room and letting it settle into a staircase of stacked cubes. Each square of the floor gets a pile of some height; piles never grow taller as you walk away from the corner, in either floor direction. That settled heap of cubes is a plane partition: a grid of numbers, one per floor square, recording how tall each pile is, with the rule that heights never increase as you move right along a row or down a column. The single corner pile is the tallest, and everything slopes away from it.

Why count these heaps? Ordinary partitions stack coins in one line of columns; plane partitions do the same thing one dimension up, stacking cubes over a flat grid. They are the natural three-dimensional cousin of the number partitions you already know, and they turn out to be controlled by a startlingly clean formula. The British combinatorialist Percy MacMahon, working a century ago, found that if you count every heap by its total number of cubes, the bookkeeping collapses into a tidy product. No messy case analysis survives; the answer is a single elegant pattern.

The payoff comes when you confine the heap to a box: at most so many rows, so many columns, and a ceiling on the height. Now you are counting the ways to stack cubes inside an $a$ -by- $b$ -by- $c$ crate so the slope rule still holds. MacMahon's box formula gives that count exactly. And the very same heaps, viewed from a corner of the crate, look like a floor tiled with three kinds of diamond-shaped tiles — so counting cube-stacks is secretly the same as counting tilings of a hexagon. One picture, two questions, one answer.

Visual Beginner

A small plane partition shown two ways: as a grid of pile-heights and as the stack of cubes it stands for. The rule is that heights do not increase left-to-right along a row, nor top-to-bottom down a column.

floor square	pile height	reading rule it obeys
top-left	$3$	tallest pile, at the corner
top-middle	$2$	not taller than the $3$ to its left
top-right	$1$	not taller than the $2$ to its left
bottom-left	$2$	not taller than the $3$ above it
bottom-middle	$1$	not taller than the $2$ above and the $2$ to its left

The total number of cubes here is $3 + 2 + 1 + 2 + 1 = 9$ . Notice every row reads downward left to right and every column reads downward top to bottom: that double slope is the entire definition. If you cap the heights at some ceiling and limit the grid to a fixed number of rows and columns, you are stacking inside a crate, and MacMahon's formula counts every legal stack at once.

Worked example Beginner

Let us count, by hand, all plane partitions that fit inside a tiny crate: at most one row, at most two columns, and heights at most $1$ . So we fill a $1$ -by- $2$ grid with heights $0$ or $1$ , weakly decreasing left to right.

Step 1. List the legal grids. The left entry is at least the right entry, and each is $0$ or $1$ . The choices are: $00$ , then $10$ , then $11$ . The grid $01$ is forbidden, because $0$ on the left is smaller than $1$ on the right, breaking the slope rule.

Step 2. Record the size of each. The grid $00$ has $0$ cubes; the grid $10$ has $1$ cube; the grid $11$ has $2$ cubes.

Step 3. Build the counting polynomial. Weight each heap by $q$ raised to its cube-count and add: $q^{0} + q^{1} + q^{2} = 1 + q + q^{2}$ .

Step 4. Compare with MacMahon's box product. For a box with $a = 1$ row, $b = 2$ columns, $c = 1$ height, the formula multiplies simple fractions indexed by the three crate directions. Worked out for these tiny numbers, the product equals $1 + q + q^{2}$ — the same three-term polynomial we just found by listing.

Step 5. Read off the plain count. Setting $q = 1$ (which just counts heaps, ignoring size) gives $1 + 1 + 1 = 3$ . There are exactly three legal heaps in this crate, matching our list.

What this tells us: the formula is not magic bookkeeping divorced from reality — for a crate small enough to check by hand, its product literally reproduces the list of heaps you can draw. The power of MacMahon's result is that the same product keeps working when the crate is far too large to enumerate by hand.

Check your understanding Beginner

Formal definition Intermediate+

Work with the partitions, Young diagrams, semistandard tableaux ( $SSYT (λ)$ ), the Schur function $s_{λ}$ , and the principal specialisation of 40.03.02, and with the RSK correspondence of 40.03.04; that notation is inherited and recorded in _meta/NOTATION.md. Fix the formal variable $q$ .

Definition (plane partition). A plane partition is an array $π = (π_{ij})_{i, j \geq 1}$ of nonnegative integers with finite support, weakly decreasing along rows and down columns: $$ \pi_{ij} \ge \pi_{i,j+1}, \qquad \pi_{ij} \ge \pi_{i+1,j}, \qquad \text{for all } i, j \ge 1. $$ Its size is $∣ π ∣ = \sum_{i, j} π_{ij}$ and its trace is $tr (π) = \sum_{i} π_{ii}$ . The three-dimensional Young diagram of $π$ is the set of lattice cubes ${(i, j, k) : 1 \leq k \leq π_{ij}}$ ; $∣ π ∣$ is its cube count. A plane partition fits in the $a \times b \times c$ box when $π_{ij} = 0$ for $i > a$ or $j > b$ , and $π_{ij} \leq c$ for all $i, j$ — equivalently its cubes lie inside $[0, a] \times [0, b] \times [0, c]$ . Write $B (a, b, c)$ for the set of plane partitions in that box.

Definition (column-strict plane partition). A column-strict plane partition is an array weakly decreasing along rows and strictly decreasing down columns. Slicing such an array by content into a chain of partitions exhibits it, via RSK, as a pair of semistandard tableaux of a common shape; this is the route the Key theorem uses.

Definition (MacMahon box generating function). For $π$ ranging over $B (a, b, c)$ , the box generating function is $\sum_{π \in B (a, b, c)} q^{∣ π ∣}$ . For $π$ ranging over all plane partitions, the MacMahon generating function is $PP (q) = \sum_{π} q^{∣ π ∣}$ , a formal power series with constant term $1$ (the empty heap).

Definition (rhombus / lozenge tiling). A lozenge is a unit rhombus formed by two adjacent triangles of the triangular lattice; it has three orientations. A lozenge tiling of a region is a partition of it into lozenges. The hexagon $H_{a, b, c}$ with side lengths $a, b, c, a, b, c$ drawn on the triangular lattice admits lozenge tilings; each tiling is the orthogonal-projection silhouette of a stack of cubes in the $a \times b \times c$ box, the three lozenge orientations recording the three visible faces of the cubes.

Counterexamples to common slips Intermediate+

"A plane partition is the same as a pair of ordinary partitions." It is a doubly-monotone array; its diagonal slices give a chain of partitions interlacing by the column rule, not an unconstrained pair. Forgetting the interlacing overcounts wildly.
"Fitting in the $a \times b \times c$ box means $∣ π ∣ \leq ab c$ ." The box constraint is dimensional, not on the total size: at most $a$ rows, at most $b$ columns, every entry $\leq c$ . A heap can have $∣ π ∣$ as large as $ab c$ (the full box) but the constraint forbids many small heaps that violate a dimension, e.g. a fourth nonzero row when $a = 3$ .
"The strict and weak versions count the same thing." Column-strict plane partitions are governed by $s_{λ} (x) s_{λ} (y)$ directly; ordinary (weakly decreasing) plane partitions need a content shift before the Schur machinery applies. Conflating the two misplaces the $q$ -exponents in the product.

Key theorem with proof Intermediate+

The signature theorem is MacMahon's box formula together with its unbounded specialisation, proved by routing the count through the Cauchy identity for Schur functions.

Theorem (MacMahon box formula). The generating function for plane partitions fitting in the $a \times b \times c$ box is $$ \sum_{\pi \in \mathcal{B}(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}} ;=; \prod_{i=1}^{a}\prod_{j=1}^{b} \frac{1 - q^{,i+j+c-1}}{1 - q^{,i+j-1}}. $$ Letting $a, b, c \to \infty$ gives the MacMahon generating function for all plane partitions, $$ \mathrm{PP}(q) ;=; \sum_{\pi} q^{|\pi|} ;=; \prod_{n \ge 1} \frac{1}{(1 - q^n)^{,n}}. $$ ^{[Stanley §7.20]}

Proof. Decompose $π$ into diagonal slices. For an integer $d$ , the diagonal $π^{(d)} = (π_{i, i + d})_{i \geq 1}$ (for $d \geq 0$ ; symmetrically for $d < 0$ ) is a partition, since the row and column rules force $π_{i, i + d} \geq π_{i + 1, i + 1 + d}$ . The doubly-monotone conditions translate into interlacing of consecutive diagonals: $π^{(d)}$ and $π^{(d + 1)}$ satisfy $π_{1}^{(d)} \geq π_{1}^{(d + 1)} \geq π_{2}^{(d)} \geq \dots$ , the relation $μ ⪰ ν$ marking a horizontal strip $μ / ν$ . A plane partition is thus a sequence of partitions $$ \varnothing ;\subseteq; \cdots ;\preceq; \lambda^{(-1)} ;\preceq; \lambda^{(0)} ;\succeq; \lambda^{(1)} ;\succeq; \cdots ;\supseteq; \varnothing $$ rising to the main diagonal $λ^{(0)}$ and falling away, each consecutive pair a horizontal strip. By the Pieri rule of 40.03.02, a chain of partitions interlacing up to $λ$ and back down, weighted by $q$ to the size, is exactly a coefficient in a product of Schur functions evaluated at a geometric specialisation. Concretely, summing $q^{∣ π ∣}$ over all such chains with central shape $λ$ yields $s_{λ} (q^{1/2}, q^{3/2}, \dots) s_{λ} (q^{1/2}, q^{3/2}, \dots)$ after the standard half-integer reindexing that converts the slice sizes into tableau contents.

Summing over $λ$ and invoking the Cauchy identity $\sum_{λ} s_{λ} (x) s_{λ} (y) = \prod_{i, j} (1 - x_{i} y_{j})^{- 1}$ of 40.03.03 with $x_{i} = q^{i - 1/2}$ , $y_{j} = q^{j - 1/2}$ gives $$ \mathrm{PP}(q) = \prod_{i, j \ge 1}\frac{1}{1 - q^{,i+j-1}} = \prod_{n \ge 1}\frac{1}{(1 - q^n)^{,n}}, $$ the last equality collecting the $n = i + j - 1$ factors, of which there are exactly $n$ pairs $(i, j)$ . Imposing the box truncates each Schur function to finitely many variables and bounds the parts; the principal specialisation $s_{λ} (1, q, \dots, q^{c})$ via the hook-content formula of 40.03.02, summed over $λ$ inside an $a \times b$ rectangle by the bounded Cauchy identity, produces the finite triple product $\prod_{i, j} (1 - q^{i + j + c - 1}) / (1 - q^{i + j - 1})$ . Reindexing $k = 1, \dots, c$ inside the telescoping ratio $\prod_{k} (1 - q^{i + j + k - 1}) / (1 - q^{i + j + k - 2})$ recovers the displayed symmetric form. $□$

Bridge. This theorem is the foundational reason plane partitions belong to this chapter rather than to elementary $q$ -series: the box count is a specialisation of the Cauchy identity, so MacMahon's product is the same statement as Schur orthonormality seen through a geometric substitution. It builds toward the nonintersecting-lattice-path determinant of Advanced results, where the Lindström-Gessel-Viennot lemma of 40.01.04 evaluates the count without symmetric functions and exposes the product as a determinant; and it appears again in the rhombus-tiling reformulation, where the same number counts lozenge tilings of a hexagon. The diagonal-slicing that turns a heap into an interlacing chain is exactly the RSK bookkeeping of 40.03.04 read three-dimensionally — column-strict plane partitions are pairs of tableaux, and that is the central insight tying the box formula to the bijection. The unbounded $\prod (1 - q^{n})^{- n}$ generalises the one-dimensional partition generating function $\prod (1 - q^{n})^{- 1}$ one exponent higher; putting these together, plane partitions are to the Cauchy identity what ordinary partitions are to the single product, the bridge being the slicing into diagonals.

Exercises Intermediate+

Exercise 6 (hard, symbolic).

Prove that the number of plane partitions in the $a \times b \times c$ box equals the number of lozenge tilings of the hexagon $H_{a, b, c}$ , by exhibiting the bijection.

Hint

Project the stack of cubes orthogonally onto a plane along the main diagonal; record which face of each cube is visible.

Answer

Place the heap of cubes for $π \in B (a, b, c)$ inside the corner of the $a \times b \times c$ crate and project orthogonally along the $(1, 1, 1)$ direction onto a plane. The crate's silhouette is a hexagon with sides $a, b, c, a, b, c$ . Each visible unit square of a cube's face projects to a unit rhombus (lozenge) of one of three orientations, according to whether the face is perpendicular to the $x$ -, $y$ -, or $z$ -axis. The visible faces tile the hexagon exactly once (every point of the hexagon is covered by precisely one nearest visible face along the projection ray), so $π$ determines a lozenge tiling. Conversely, a lozenge tiling assigns to each column of the projection a height profile recovering the $π_{ij}$ uniquely, since the three orientations of lozenges encode the local steps of the surface and a tiling of the simply-connected hexagon integrates to a single-valued height function (the cube surface). The two maps are mutually inverse, giving a bijection. Hence the box count equals the lozenge-tiling count, both $\prod_{i, j, k} \frac{i + j + k - 1}{i + j + k - 2}$ . Rubric: full credit for the projection map, the height-function inverse, and the equality of counts.

Exercise 7 (hard, symbolic).

Derive the box formula by the Lindström-Gessel-Viennot lemma: model the lozenge tiling as $b$ nonintersecting lattice paths and evaluate the resulting determinant at $q = 1$ as a product.

Hint

The lozenges of one fixed orientation, strung together, form nonintersecting monotone lattice paths between $b$ sources and $b$ sinks on the hexagon boundary; apply LGV and recognise the determinant as a Lindström-type evaluation.

Answer

In the hexagon $H_{a, b, c}$ , mark the lozenges of one chosen orientation; their union forms $b$ disjoint monotone lattice paths $P_{1}, \dots, P_{b}$ joining $b$ equally spaced sources $A_{j}$ on one side to $b$ sinks $B_{j}$ on the opposite side, and a lozenge tiling is the same data as a family of such paths that do not touch. By the Lindström-Gessel-Viennot lemma of 40.01.04, the (weighted) count of nonintersecting families equals $det (M_{j k})$ where $M_{j k}$ is the path-generating function $A_{j} \to B_{k}$ , a binomial $(\cdot a + c)$ at $q = 1$ . The matrix is a determinant of binomial coefficients of Lindström / Gessel-Viennot type; its value evaluates by the standard Lindström determinant to $\prod_{i = 1}^{a} \prod_{j = 1}^{b} \prod_{k = 1}^{c} \frac{i + j + k - 1}{i + j + k - 2}$ , the box count. Equivalently this is the $q = 1$ specialisation of the Schur/Jacobi-Trudi determinant computing $s_{λ}$ over the rectangle, the two proofs meeting at the same determinant. Rubric: full credit for the path model, the LGV determinant, and its product evaluation matching MacMahon.

Advanced results Master

The box formula organises into a symmetry-class theory, a tiling / limit-shape geometry, an alternating-sign-matrix theorem, and a bijective correspondence for the reverse (weakly increasing) variant.

Theorem 1 (the ten symmetry classes). The cyclic group of the cube and the complementation $π_{ij k} \mapsto 1 - π_{(a + 1 - i) (b + 1 - j) (c + 1 - k)}$ generate a group of symmetries of $B (a, b, c)$ (for cubic boxes the relevant group includes the rotation cycling the three axes and the transpose); orbits define ten symmetry classes of plane partitions — unrestricted, transpose-symmetric, cyclically symmetric, totally symmetric, self-complementary, and their compatible combinations. Each class has a product enumeration formula. The unrestricted case is MacMahon; the remaining nine were conjectured by Andrews, Macdonald, and Mills-Robbins-Rumsey and proved over the following two decades, the most stubborn being the totally-symmetric-self-complementary class. For instance the number of cyclically symmetric plane partitions in $B (a, a, a)$ is $\prod_{i = 1}^{a} \frac{3 i - 1}{3 i - 2} \prod_{1 \leq i \leq j \leq a} \frac{i + j + a - 1}{2 i + j - 1}$ (Andrews-Macdonald) ^{[Bressoud 1999]}. The proofs run through nonintersecting paths, the six-vertex model, and constant-term identities.

Theorem 2 (rhombus tilings and the arctic-circle limit shape). Plane partitions in $B (a, b, c)$ are in bijection with lozenge tilings of the hexagon $H_{a, b, c}$ , and (via a further bijection) with families of nonintersecting paths, with dimer coverings of a hexagonal region, and with the rhombus / domino tilings studied in statistical mechanics. Under the uniform measure on tilings of the scaled hexagon $H_{N a, N b, N c}$ as $N \to \infty$ , the typical tiling freezes outside an inscribed ellipse and is disordered inside it: the boundary between the frozen and liquid regions converges to the ellipse inscribed in the hexagon, the arctic-circle / arctic-ellipse phenomenon. This is the limit-shape counterpart of MacMahon's exact enumeration, computed by Cohn, Larsen, and Propp via the exact correlation kernel ^{[Cohn-Larsen-Propp 1998]}.

Theorem 3 (alternating sign matrices). An alternating sign matrix (ASM) of order $n$ is an $n \times n$ matrix with entries in ${0, 1, - 1}$ whose nonzero entries alternate in sign along every row and column and sum to $1$ in each row and column. The number of ASMs of order $n$ is $$ A_n ;=; \prod_{k=0}^{n-1} \frac{(3k+1)!}{(n+k)!}, $$ the alternating-sign-matrix theorem, conjectured by Mills, Robbins, and Rumsey (1983) after observing that $A_{n}$ also counts certain descending plane partitions and totally-symmetric-self-complementary plane partitions, and first proved by Zeilberger (1996) and independently by Kuperberg (1996) using the six-vertex model and the Yang-Baxter equation. ASMs, monotone triangles, the square-ice model, and TSSCPP are four faces of the same enumeration ^{[Bressoud 1999]}.

Theorem 4 (Hillman-Grassl and reverse plane partitions). A reverse plane partition of shape $λ$ is a filling of the Young diagram of $λ$ with nonnegative integers weakly increasing along rows and down columns. The Hillman-Grassl correspondence is a bijection between reverse plane partitions of shape $λ$ and arrays of nonnegative integers indexed by the cells of $λ$ , under which the size of the reverse plane partition equals the hook-length-weighted sum of the array. It yields the generating function $$ \sum_{\text{rpp of shape }\lambda} q^{|\pi|} ;=; \prod_{(i,j)\in\lambda}\frac{1}{1 - q^{,h(i,j)}}, $$ where $h (i, j)$ is the hook length, the hook generating function for reverse plane partitions and the $q$ -analogue refinement of the hook-length formula of 40.03.02.

Synthesis. Putting these together, MacMahon's product is the visible tip of a symmetry-class theory in which the same cube can be counted ten ways. The foundational reason all of these are products is the determinantal structure: every model — interlacing partition chains, nonintersecting lattice paths, lozenge tilings, the six-vertex configurations of the ASM proofs — reduces by the Lindström-Gessel-Viennot lemma of 40.01.04 or the Yang-Baxter equation to a determinant or constant-term identity that evaluates to a hook-content product. This is exactly the principal-specialisation reading: the box formula is dual to the Cauchy identity of 40.03.03 through the substitution $x_{i} = q^{i - 1/2}$ , and the diagonal slicing that establishes it is the RSK bookkeeping of 40.03.04 in three dimensions. The central insight is that exact enumeration (MacMahon, Andrews-Macdonald-Mills-Robbins-Rumsey, the ASM theorem) and limit shape (the arctic ellipse of Theorem 2) are the two faces of one integrable structure: the determinantal correlation kernel that makes the lozenge tiling a determinantal point process is the same kernel whose trace gives the partition function. The Hillman-Grassl correspondence of Theorem 4 is dual to this, refining the count by hook lengths, and it generalises into the broader $P$ -partition theory of 40.01.04; the bridge is that hooks, contents, and the Cauchy product are three readings of the same Schur specialisation.

Full proof set Master

Proposition 1 (diagonal slices interlace). For a plane partition $π$ , each diagonal $λ^{(d)} = (π_{i, i + d})_{i}$ (with the symmetric convention for $d < 0$ ) is a partition, and consecutive diagonals interlace: $λ^{(d)} / λ^{(d + 1)}$ and $λ^{(d + 1)} / λ^{(d)}$ are horizontal strips.

Proof. Fix $d \geq 0$ . Monotonicity down columns gives $π_{i, i + d} \geq π_{i + 1, i + d}$ and along rows $π_{i + 1, i + d} \geq π_{i + 1, i + 1 + d}$ , so $π_{i, i + d} \geq π_{i + 1, i + 1 + d}$ : the entries of $λ^{(d)}$ weakly decrease, hence form a partition. For interlacing, compare $λ^{(d)} = (π_{i, i + d})_{i}$ with $λ^{(d + 1)} = (π_{i, i + d + 1})_{i}$ . The row rule gives $π_{i, i + d} \geq π_{i, i + d + 1}$ , i.e. $λ_{i}^{(d)} \geq λ_{i}^{(d + 1)}$ ; the column rule applied diagonally gives $π_{i, i + d + 1} \geq π_{i + 1, i + d + 1} = λ_{i + 1}^{(d + 1)}$ together with $π_{i, i + d + 1} \leq π_{i, i + d}$ , assembling into $λ_{i}^{(d)} \geq λ_{i}^{(d + 1)} \geq λ_{i + 1}^{(d)}$ . This is precisely the condition that $λ^{(d)} / λ^{(d + 1)}$ is a horizontal strip (at most one cell per column). The mirror computation handles $d < 0$ , and the diagonals rise to $λ^{(0)}$ on the main diagonal and fall to $\emptyset$ on both ends. $□$

Proposition 2 (the MacMahon generating function). $π \sum q^{∣ π ∣} = n \geq 1 \prod (1 - q^{n})^{- n}$ .

Proof. By Proposition 1 a plane partition is a bi-infinite interlacing sequence of partitions $(λ^{(d)})_{d \in Z}$ , eventually empty in both directions, with $λ^{(d)} ⪰ λ^{(d + 1)}$ for $d \geq 0$ and $λ^{(d - 1)} ⪯ λ^{(d)}$ for $d \leq 0$ , where $⪰$ denotes a horizontal strip. The size is $∣ π ∣ = \sum_{d} ∣ λ^{(d)} ∣$ . Assign the slice $λ^{(d)}$ the variable $x_{?}$ in the half-integer indexing $x_{i} = q^{i - 1/2}$ on the falling side and $y_{j} = q^{j - 1/2}$ on the rising side. The Pieri rule of 40.03.02 states that summing $\prod q^{∣ λ^{(d)} ∣}$ over all chains rising to a fixed $λ$ produces $s_{λ}$ evaluated at the geometric sequence, and likewise on the falling side; the central shape $λ = λ^{(0)}$ is shared. Hence $$ \sum_\pi q^{|\pi|} = \sum_\lambda s_\lambda(q^{1/2}, q^{3/2}, \dots), s_\lambda(q^{1/2}, q^{3/2}, \dots). $$ Apply the Cauchy identity $\sum_{λ} s_{λ} (x) s_{λ} (y) = \prod_{i, j} (1 - x_{i} y_{j})^{- 1}$ of 40.03.03 with $x_{i} = q^{i - 1/2}$ , $y_{j} = q^{j - 1/2}$ : the product is $\prod_{i, j \geq 1} (1 - q^{i + j - 1})^{- 1}$ . Collecting factors with $i + j - 1 = n$ , of which there are $n$ , gives $\prod_{n} (1 - q^{n})^{- n}$ . $□$

Proposition 3 (the box formula). $π \in B (a, b, c) \sum q^{∣ π ∣} = i = 1 \prod a j = 1 \prod b \frac{1 - q ^{i + j + c - 1}}{1 - q ^{i + j - 1}}$ .

Proof. The box constraints restrict the interlacing chain of Proposition 2: at most $a$ rows bounds each $λ^{(d)}$ to $\leq a$ parts, so the Schur functions use only the variables $x_{1}, \dots, x_{a}$ ; entries $\leq c$ caps the largest part; at most $b$ columns confines $λ^{(0)}$ to a $b$ -bounded width. The sum becomes $\sum_{λ \subseteq (b^{a})} s_{λ} (q^{1/2}, \dots, q^{a - 1/2}) s_{λ} (\tilde{q})$ over $λ$ inside the $a \times b$ rectangle with parts $\leq c$ , which is the bounded Cauchy identity $\sum_{λ \subseteq (b^{a})} s_{λ} (x_{1}, \dots, x_{a}) s_{λ} (y_{1}, \dots, y_{b}) = \prod_{i = 1}^{a} \prod_{j = 1}^{b} (1 - x_{i} y_{j})^{- 1}$ truncated by the height $c$ . Evaluating the principal specialisations through the hook-content formula $s_{λ} (1, q, \dots, q^{c}) = q^{n (λ)} \prod_{(i, j) \in λ} \frac{1 - q ^{c + 1 + c (i, j)}}{1 - q ^{h (i, j)}}$ of 40.03.02 and resumming gives $\prod_{i = 1}^{a} \prod_{j = 1}^{b} \frac{1 - q ^{i + j + c - 1}}{1 - q ^{i + j - 1}}$ . Telescoping each factor as $\frac{1 - q ^{i + j + c - 1}}{1 - q ^{i + j - 1}} = \prod_{k = 1}^{c} \frac{1 - q ^{i + j + k - 1}}{1 - q ^{i + j + k - 2}}$ recovers the symmetric triple product, manifestly symmetric in $(a, b, c)$ . As $c \to \infty$ each factor tends to $(1 - q^{i + j - 1})^{- 1}$ and the box formula limits to Proposition 2. $□$

Proposition 4 (column-strict plane partitions are pairs of SSYT). Column-strict plane partitions with parts $\leq n$ and at most $m$ columns biject with pairs $(P, Q)$ of semistandard tableaux of equal shape, $P$ with entries $\leq n$ and $Q$ with entries $\leq m$ , the size matching the combined content; consequently their generating function is $\sum_{λ} s_{λ} (x) s_{λ} (y)$ .

Proof. A column-strict plane partition is weakly decreasing along rows and strictly decreasing down columns. Read its successive layers ${(i, j) : π_{ij} \geq k}$ for $k = 1, 2, \dots$ : strict column decrease forces each layer to be a Young diagram with the layers nested $λ^{[1]} \supseteq λ^{[2]} \supseteq \dots$ , and the difference of consecutive layers is a horizontal strip (weak row decrease). This nested sequence of horizontal strips is exactly the data of a semistandard tableau $P$ recording, in cell $(i, j)$ , the largest $k$ with $(i, j) \in λ^{[k]}$ . The transpose reading (by the strict/weak roles exchanged) produces a second tableau $Q$ of the same shape. This is the RSK decomposition of 40.03.04 applied to the matrix of the plane partition: RSK sends the supporting $N$ -matrix to $(P, Q)$ of equal shape with the content bookkeeping. Tracking $q$ -weights, the size becomes the sum of contents, so the generating function is $\sum_{λ} (\sum_{P} x^{content (P)}) (\sum_{Q} y^{content (Q)}) = \sum_{λ} s_{λ} (x) s_{λ} (y)$ by the combinatorial definition of $s_{λ}$ in 40.03.02. $□$

Proposition 5 (Hillman-Grassl generating function). For a partition shape $λ$ , $rpp of shape λ \sum q^{∣ π ∣} = (i, j) \in λ \prod (1 - q^{h (i, j)})^{- 1}$ .

Proof. The Hillman-Grassl algorithm reads a reverse plane partition $π$ of shape $λ$ and produces a nonnegative-integer array $A = (a_{ij})_{(i, j) \in λ}$ by repeatedly extracting hook-shaped strips: locate the most-northwest nonzero cell, subtract $1$ along a canonical lattice path tracing a hook, and increment the corresponding $a_{ij}$ . Each extraction along the hook at cell $(i, j)$ removes exactly $h (i, j)$ from $∣ π ∣$ per unit of $a_{ij}$ , and the algorithm is invertible (the reverse builds $π$ from $A$ by adding the hook paths in the reverse order), giving a bijection between reverse plane partitions and arrays $A \in N^{λ}$ with $∣ π ∣ = \sum_{(i, j)} h (i, j) a_{ij}$ . Therefore $$ \sum_{\text{rpp}} q^{|\pi|} = \sum_{A \in \mathbb{N}^\lambda} q^{\sum h(i,j) a_{ij}} = \prod_{(i,j)\in\lambda}\sum_{a\ge0} q^{h(i,j) a} = \prod_{(i,j)\in\lambda}\frac{1}{1 - q^{h(i,j)}}. \qquad \square $$

Connections Master

This unit is built directly on the Schur functions, the principal specialisation, and the hook-content formula of 40.03.02: the diagonal-slice interlacing is governed by the Pieri rule, the box count is the bounded Cauchy sum of principal specialisations $s_{λ} (1, q, \dots, q^{c})$ , and the Hillman-Grassl product $\prod (1 - q^{h (i, j)})^{- 1}$ is the $q$ -refinement of the hook-length formula proved there. The column-strict bijection of the Full proof set is the RSK correspondence of 40.03.04 read three-dimensionally — a plane partition is a chain of horizontal strips, the same nested-strip data that RSK packages as a pair of semistandard tableaux.
The Cauchy identity $\sum_{λ} s_{λ} (x) s_{λ} (y) = \prod_{i, j} (1 - x_{i} y_{j})^{- 1}$ of 40.03.03, specialised at $x_{i} = q^{i - 1/2}$ , $y_{j} = q^{j - 1/2}$ , is exactly MacMahon's $\prod (1 - q^{n})^{- n}$ , so the box formula and Schur orthonormality are one statement; and the nonintersecting-lattice-path determinant that proves the formula without symmetric functions is the Lindström-Gessel-Viennot lemma of 40.01.04, the same determinant that there computes transfer matrices and $P$ -partition generating functions. The quasisymmetric-function refinement of 40.03.08 expresses these $P$ -partition and plane-partition generating functions in the monomial quasisymmetric basis, sharpening the symmetric-function identities used here into the finer $QSym$ algebra.
The analytic asymptotics of the plane-partition count — the size- $n$ coefficient of $\prod (1 - q^{n})^{- n}$ grows like a stretched exponential with a known constant, the three-dimensional analogue of the Hardy-Ramanujan partition asymptotic — are obtained by the saddle-point and circle-method techniques of 21.16.02, applied to the MacMahon generating function in place of the Euler product, whose own asymptotics rest on the partition generating function of 21.16.01. The arctic-ellipse limit shape of the boxed plane partitions is the geometric face of those asymptotics, and the determinantal point process governing the lozenge tilings is the combinatorial cousin of the random-matrix spectra that recur across mathematical physics.

Historical & philosophical context Master

Plane partitions were introduced by Percy Alexander MacMahon in a series of memoirs from 1896 onward, gathered in his 1916 treatise Combinatory Analysis ^{[MacMahon 1916]}, where he stated and proved the box generating function and conjectured several of the symmetry-class enumerations on the strength of extensive hand computation. MacMahon's own proof of the box formula used his "method of partitions" and the algebra of symmetric functions; the modern routing through the Cauchy identity and the Lindström-Gessel-Viennot determinant clarifies that his product is a principal specialisation of Schur-function orthonormality.

The symmetry classes were systematised by Richard Stanley in a 1986 survey, and the outstanding conjectures were settled over the next decade: George Andrews and Ian Macdonald proved the cyclically symmetric cases, and William Mills, David Robbins, and Howard Rumsey conjectured the alternating-sign-matrix enumeration $A_{n} = \prod_{k = 0}^{n - 1} (3 k + 1)! / (n + k)!$ in 1983 after noticing that the same numbers count descending plane partitions. The ASM conjecture was proved by Doron Zeilberger in 1996 in a famously long checked-by-referees argument, and independently and more briefly by Greg Kuperberg the same year using the six-vertex (square-ice) model of statistical mechanics and the Yang-Baxter equation, exhibited at book length by David Bressoud ^{[Bressoud 1999]}. The limit-shape side was opened by Henry Cohn, Michael Larsen, and James Propp in 1998 ^{[Cohn-Larsen-Propp 1998]}, who computed the arctic-ellipse boundary for boxed plane partitions via the exact lozenge-tiling correlation kernel.

Bibliography Master

@book{stanley1999ec2,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 2},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {62},
  publisher = {Cambridge University Press},
  year      = {1999}
}

@book{macdonald1995symmetric,
  author    = {Macdonald, Ian G.},
  title     = {Symmetric Functions and Hall Polynomials},
  series    = {Oxford Mathematical Monographs},
  edition   = {2},
  publisher = {Oxford University Press},
  year      = {1995}
}

@book{macmahon1916,
  author    = {MacMahon, Percy A.},
  title     = {Combinatory Analysis, Volumes I and II},
  publisher = {Cambridge University Press},
  year      = {1916}
}

@book{bressoud1999proofs,
  author    = {Bressoud, David M.},
  title     = {Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture},
  series    = {Spectrum Series},
  publisher = {Cambridge University Press and the Mathematical Association of America},
  year      = {1999}
}

@article{cohnlarsenpropp1998,
  author  = {Cohn, Henry and Larsen, Michael and Propp, James},
  title   = {The shape of a typical boxed plane partition},
  journal = {New York Journal of Mathematics},
  volume  = {4},
  pages   = {137--165},
  year    = {1998}
}

@article{millsrobbinsrumsey1983,
  author  = {Mills, William H. and Robbins, David P. and Rumsey, Howard},
  title   = {Alternating sign matrices and descending plane partitions},
  journal = {Journal of Combinatorial Theory, Series A},
  volume  = {34},
  number  = {3},
  pages   = {340--359},
  year    = {1983}
}

@article{zeilberger1996asm,
  author  = {Zeilberger, Doron},
  title   = {Proof of the alternating sign matrix conjecture},
  journal = {Electronic Journal of Combinatorics},
  volume  = {3},
  number  = {2},
  pages   = {R13},
  year    = {1996}
}

@article{kuperberg1996asm,
  author  = {Kuperberg, Greg},
  title   = {Another proof of the alternating-sign matrix conjecture},
  journal = {International Mathematics Research Notices},
  volume  = {1996},
  number  = {3},
  pages   = {139--150},
  year    = {1996}
}

@article{hillmangrassl1976,
  author  = {Hillman, A. P. and Grassl, R. M.},
  title   = {Reverse plane partitions and tableau hook numbers},
  journal = {Journal of Combinatorial Theory, Series A},
  volume  = {21},
  number  = {2},
  pages   = {216--221},
  year    = {1976}
}

Prerequisites

40.03.02
40.03.04

Tier anchors

beginner: Stanley 1999 *Enumerative Combinatorics, Volume 2* (Cambridge) §7.20 opening (plane partitions as weakly decreasing arrays and the stack-of-cubes picture, MacMahon's product by small examples); Bressoud 1999 *Proofs and Confirmations* (Cambridge / MAA) Ch. 1-2 (plane partitions, boxed plane partitions, and the lozenge-tiling reformulation by worked pictures)
intermediate: Stanley 1999 *Enumerative Combinatorics, Volume 2* 2e (Cambridge) §7.20-7.21 (plane partitions, column-strict plane partitions as pairs of SSYT, the MacMahon box generating function $\prod (1-q^{i+j+k-1})/(1-q^{i+j+k-2})$ and the unbounded $\prod(1-q^n)^{-n}$, the Lindström-Gessel-Viennot and Schur-function proofs); Bressoud 1999 *Proofs and Confirmations* (Cambridge / MAA) Ch. 2-7 (the symmetry classes, the rhombus-tiling bijection, and the alternating-sign-matrix theorem)
master: Stanley 1999 *Enumerative Combinatorics, Volume 2* 2e (Cambridge) §7.20-7.22, Appendix (plane partitions and their symmetry classes, the box formula by RSK and by nonintersecting lattice paths, the Hillman-Grassl correspondence and the trace generating function); Macdonald 1995 *Symmetric Functions and Hall Polynomials* 2e (Oxford) Ch. I §5 Ex. (the box formula as a principal specialisation of the Cauchy identity); Bressoud 1999 *Proofs and Confirmations* (Cambridge / MAA) (the ten symmetry classes and the Andrews-Macdonald-Mills-Robbins-Rumsey enumerations, the ASM theorem of Zeilberger); MacMahon 1916 *Combinatory Analysis* (Cambridge); Cohn-Larsen-Propp 1998 *New York J. Math.* 4 (the arctic-circle and limit-shape phenomenon for boxed plane partitions)

References

Stanley, R. P. — Enumerative Combinatorics, Volume 2 · Cambridge Studies in Advanced Mathematics 62 (1999). Chapter 7 §7.20 defines a plane partition as an array $\pi = (\pi_{ij})_{i,j \ge 1}$ of nonnegative integers, finitely supported, weakly decreasing along rows ($\pi_{ij} \ge \pi_{i,j+1}$) and down columns ($\pi_{ij} \ge \pi_{i+1,j}$); its size $|\pi| = \sum \pi_{ij}$ and its three-dimensional Young-diagram (stack of unit cubes) interpretation. The generating function for all plane partitions is MacMahon's $\sum_\pi q^{|\pi|} = \prod_{n \ge 1}(1 - q^n)^{-n}$. §7.20-7.21 prove the box formula: the generating function for plane partitions fitting inside an $a \times b \times c$ box (at most $a$ rows, $b$ columns, entries $\le c$) is $\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}}$, with the symmetric product form $\prod_{i=1}^a\prod_{j=1}^b \frac{1 - q^{i+j+c-1}}{1 - q^{i+j-1}}$; the unbounded limit recovers $\prod(1-q^n)^{-n}$. Two proofs are given: column-strict plane partitions biject (by RSK / the Lindström-Gessel-Viennot nonintersecting-path determinant) with the Schur-function side, and the box count is the principal specialisation $s_\lambda(1, q, \dots, q^{c})$ summed via the Cauchy identity $\sum_\lambda s_\lambda(x) s_\lambda(y)$. The trace generating function $\sum_\pi q^{|\pi|} z^{\mathrm{tr}(\pi)}$, the Hillman-Grassl correspondence for reverse plane partitions (§7.22), the symmetry classes, the connection to rhombus (lozenge) tilings of a hexagon, and the alternating-sign-matrix enumeration are developed in §7.21-7.23 and the notes.
Bressoud, D. M. — Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture · Cambridge University Press / Mathematical Association of America, Spectrum Series (1999). Develops plane partitions and their ten symmetry classes from MacMahon through the alternating-sign-matrix theorem: Ch. 1-2 introduce plane partitions, boxed plane partitions inside an $a\times b\times c$ box, the lozenge (rhombus) tiling of a hexagon as the equivalent model, and MacMahon's box formula. Later chapters treat the symmetry classes (plane, transpose-, cyclic-, complement-symmetric and their combinations) enumerated by the Andrews-Macdonald-Mills-Robbins-Rumsey product formulas, the descending-plane-partition and totally-symmetric-self-complementary-plane-partition (TSSCPP) models, the alternating-sign-matrix conjecture of Mills-Robbins-Rumsey, and its proofs by Zeilberger (1996) and Kuperberg (1996, via the six-vertex model and the Yang-Baxter equation). The arctic-circle phenomenon for boxed plane partitions / domino and lozenge tilings is discussed as the limit-shape counterpart of the exact enumeration.
Macdonald, I. G. — Symmetric Functions and Hall Polynomials · Oxford Mathematical Monographs, 2nd edition (1995). Chapter I §5 and its examples treat plane partitions as a principal specialisation of symmetric-function identities: the generating function for column-strict plane partitions is a sum of products of Schur functions $s_\lambda(x) s_\lambda(y)$ specialised at geometric progressions $x_i = q^{i}$, $y_j = q^{j}$, so the Cauchy identity $\sum_\lambda s_\lambda(x) s_\lambda(y) = \prod_{i,j}(1 - x_i y_j)^{-1}$ yields MacMahon's product. The principal specialisation $s_\lambda(1, q, \dots, q^{n-1})$ via the hook-content formula supplies the finite-box version, and the involution $\omega$ and the dual Cauchy identity give the column-strict / row-strict transpose statements. The relevant determinantal input is the Jacobi-Trudi formula and its nonintersecting-path (Lindström-Gessel-Viennot) reading.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m