Plane partitions, Lozenge tiling, and MacMahon’s formula

Recall a partition is given by a sequence of weakly decreasing, positive integers ${\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_l >0}$. A plane partition, on the other hand, is given by a Young tableau like object where each row and each column is weakly decreasing, with repeated values allowed. In other words, ${\pi = \pi_{ij}}$ is a plane partition if ${\pi_{ij} \ge \pi_{i,j+1}}$ and ${\pi_{ij} \ge \pi_{i+1,j}}$. Since we are thinking of ${\pi}$ as a subset of an infinite 2-dimensional array, where empty space stands for ${0}$, it has the shape of a Ferrers diagram. As an example, let

$\displaystyle \pi = \begin{array}{cccccccc} 7&5&5&3&2&1&1&1 \\ 6&5&5&2&1&1&&\\ 6&3&2&2&&&& \end{array}. \ \ \ \ \ (1)$

Then ${|\pi| = 58}$, the shape of ${\pi}$, denoted ${\rm{Sh}(\pi)}$ is ${(8,6,4)}$, ie., the row lengths vector. It has a total of 18 parts, with 8 columns and 3 rows. The trace ${\rm{Tr}(\pi) = 7+5+2 = 14}$. One can think of it as the tiling of hexagons, or boxes in a room by the following result. A key reference is the shape of a typical boxed plane partition by Cohn, Larsen, and Propp. Viewing it as tiling of hexagons, the arctic circle phenomenon emerges.

Equivalently, one considers an order ideal ${I \subset {\mathbb N}^3}$, which means if ${(i,j,k) \in I}$, then ${(i',j',k') \in I}$ as well for any ${i' \le i, j' \le j, k' \le k}$. ${I}$ corresponds with plane partitions in the following way:

$\displaystyle \pi_{ij} = |\{k:(i,j,k) \in I \exists i,j\}|. \ \ \ \ \ (2)$

Now let ${\mathcal{P}(r,c)}$ be the set of ${\pi}$ with at most ${r}$ rows and ${c}$ columns. Thus ${\mathcal{P}(1,c)}$ is the collection of ordinary partitions with at most c parts, and trace of ${\lambda \in \mathcal{P}(1,c)}$ is just the biggest part (or the total number of parts?).
Fact: ${ \sum_{\pi \in \mathcal{P}(1,c)} q^{\rm{Tr}(\pi)} x^{|\pi|} = \prod_{i=1}^c \frac{1}{1-qx^i}}$, true by inspection: pick term from each factor on the right hand side expanded out geometrically; the q exponent keeps track of the total number of parts, and the x exponent the sum of the parts.

As a generalization, we have the main theorem of today:

Theorem 1

$\displaystyle \sum_{\pi \in \mathcal{P}(r,c)} q^{\rm{Tr}(\pi)} x^{|\pi|} = \prod_{i=1}^r \prod_{j=1}^c \frac{1}{1- q x^{i+j-1}} \ \ \ \ \ (3)$

Corollary 2 Set ${q=1}$, and let ${r,c \rightarrow \infty}$, then

$\displaystyle \sum_n |\{\pi: |\pi|=n\}| x^n = \frac{1}{1-x} \frac{1}{(1-x^2)^2} \frac{1}{(1-x^3)^3} \ldots = \prod_{i=1}^\infty \frac{1}{(1-x^i)^i}. \ \ \ \ \ (4)$

Proof: by fooling with RSK algorithm, but only towards the end.

1. Given ${\lambda,\mu}$ partitions into distinct parts with the same total number of parts ${l(\lambda) = l(\mu)}$, build a new partition ${\rho(\lambda,\mu)}$ as follows. Shift the ith rows of ${\lambda}$ and ${\mu}$ by ${i-1}$ dots to the right, so that a 45 degree diagonal emerges on the left most edge of each diagram. Call the new oblique diagrams ${\tilde{\lambda}}$ and ${\tilde{\mu}}$. Next reflect ${\tilde{\mu}}$ across that diagonal and glue it to ${\tilde{\lambda}}$ along that diagonal:

$\displaystyle \left[\begin{array}{ccccc} &&\lambda &&\\ *&*&*&*&*\\*&*&*&&\\ *&*&&&\end{array}\right] + \left[\begin{array}{cccccc} &&\mu&&&\\ *&*&*&*&*&*\\ *&*&&&&\\ *&&&&& \end{array} \right] \ \ \ \ \ (5)$

$\displaystyle \rightarrow \left[\begin{array}{ccccc} && \tilde{\lambda} && \\ *&*&*&*&*\\ &*&*&*&\\ &&*&*& \end{array} \right] + \left[\begin{array}{cccccc} &&\tilde{\mu}&&&\\ *&*&*&*&*&*\\ &*&*&&&\\ &&*&&& \end{array} \right] \ \ \ \ \ (6)$

$\displaystyle \overset{\rm{glue}}{\rightarrow} \left[\begin{array}{ccccc} &&\rho(\lambda,\mu) && \\ *&*&*&*&* \\ *&*&*&*&\\ *&*&*&*&\\ *&&&&\\*&&&&\\*&&&& \end{array}\right]. \ \ \ \ \ (7)$

This gives a new partition of size ${|\lambda| + |\mu| - l(\lambda)}$. For instance ${\rho(532,621) = 5,4^2,1^3}$ as above.

2. A reverse SSYT(rSSYT) has weakly decreasing rows and strictly decreasing columns (instead of increasing as for SSYT). Given ${P,Q}$ both rSSYT of the same shape, we create a plane partition ${\rho(P,Q)}$ by doing step 1 as follows: the rth columns of ${P}$ and ${Q}$ are partitions of distinct parts and the same number of parts. So performing the diagonal gluing, we get a new partition. Write its row size down the rth column of the plane partition ${\rho(P,Q)}$. Since ${P,Q}$ have the same shape, their columns match up. So this procedure is certainly well-defined.
3. Now define ${\pi'}$ from ${\pi}$ by taking transpose of each row (why this is needed is not clear to me). A fact not proven is that ${(P,Q) \leftrightarrow \pi'}$ is a bijection between pairs of rSSYTs of the same shape and plane partitions. Obviously

$\displaystyle |\pi'| = |P| + |Q| - |\rm{Sh}(P)|, \ \ \ \ \ (8)$

Also ${\rm{Diag}(\pi') = \rm{Sh}(P) = \rm{Sh}(Q)}$. The number of rows in ${\pi'}$ is the maximum among all entries of ${Q}$, and number of columns of ${\pi'}$ is the maximum entry in ${P}$.

4. Finally we get to RSK: RSK for tables. Recall given a two-way infinite array (table), we can write down a 2-line array by recording from left to right top to bottom the coordinates of the nonzero entries for a number of times equal to the entry in that table (so 0 is in fact a special case). Then we perform RSK on that 2-line array to obtain two SSYTs (so ${P}$ consists of numbers in the top row, and ${Q}$ consists of numbers in the bottom row). To get two rSSYTs ${P}$ and ${Q}$ instead, we reverse the inequality signs in the RSK procedure (so it seeks longest decreasing subsequence etc instead of increasing).

This procedure gives a bijection between ${r \times c}$ ${{\mathbb N}}$-valued tables and pairs of rSSYT’s in ${\mathcal{P}(r,c)}$. Note that ${|P| = \sum_{ij} j a_{ij}}$ and ${|Q| = \sum_{ij} i a_{ij}}$. Also ${|\rm{Sh}(P)| =|\rm{Sh}(Q)| = \sum a_{ij}}$. So together with the previous bijection with plane partitions, we get

$\displaystyle \sum_{\pi \in \mathcal{P}(r,c)} q^{\rm{Tr}(\pi)} x^{|\pi|} = \sum_{A = (a_{ij}) \in \mathcal{M}_{r,c}} q^{\sum a_{ij}} x^{\sum (i+j) a_{ij} - \sum a_{ij}} \\ = \prod_{i=1}^r \prod_{j=1}^c \sum_{a_{ij} \ge 0} q^{a_{ij}} x^{(i+j-1) a_{ij}} = \prod_{i,j=1}^{r,c} (1-q x^{i+j-1})^{-1} \ \ \ \ \ (9)$

$\Box$

An additional fact: fix ${r,c,t}$, ${r \le c}$, let ${\mathcal{M}(r,c,t)}$ be the number of plane partitions that fit into an ${r\times c \times t}$ box, then

Theorem 3 (MacMahon)

$\displaystyle \mathcal{M}(r,c,t) = \prod_{i=1}^r \prod_{j=1}^c \prod_{k=1}^t \frac{i+j+k-1}{i+j+k-2} \ \ \ \ \ (10)$

If we impose certain symmetry requirement for the plane partition, the counting problem becomes more interesting (see J. Stembridge, Adv. Math 1995). Think of ${\pi}$ as an order ideal in ${{\mathbb N}^3}$. Then ${S_3}$ acts on it by permutation coordinates. In fact ${D_6}$ is the full symmetry group of order ideals, with the additional 2-fold symmetry given by taking complement over the smallest box containing the ideal. Nice formulae come out of enumeration of invariant plane partitions under various subgroups of ${D_6}$.

math PhD at Stanford, studying probability
This entry was posted in algebraic combinatorics, Uncategorized and tagged , , . Bookmark the permalink.

3 Responses to Plane partitions, Lozenge tiling, and MacMahon’s formula

1. Abhay says:

Hi,
Macmahon had given a formula for perfect partitions of any integer ‘n’. Can you exemplify that for me.
It said, every integer can be written in the form of:

n = (p1^a1) * (p2^a2) * ……. * (pm^am) – 1
then perfect_partitions(n) = compositions of a1*a2*…..*an

for n = 95, i get answer as 16 but correct answer is 112. If you can explain

Thanks

• Abhay says:

In my previous post, p1, p2, p3, ….., pn all are distinct primes

• Hi Abhay,
I am afraid I don’t know much about perfect partitions. Could you motivate the definition a bit more?