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

Advertisements

About aquazorcarson

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s