Recall a partition is given by a sequence of weakly decreasing, positive integers . 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, is a plane partition if and . Since we are thinking of as a subset of an infinite 2-dimensional array, where empty space stands for , it has the shape of a Ferrers diagram. As an example, let
Then , the shape of , denoted is , ie., the row lengths vector. It has a total of 18 parts, with 8 columns and 3 rows. The trace . 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 , which means if , then as well for any . corresponds with plane partitions in the following way:
Now let be the set of with at most rows and columns. Thus is the collection of ordinary partitions with at most c parts, and trace of is just the biggest part (or the total number of parts?).
Fact: , 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:
Corollary 2 Set , and let , then
Proof: by fooling with RSK algorithm, but only towards the end.
- Given partitions into distinct parts with the same total number of parts , build a new partition as follows. Shift the ith rows of and by dots to the right, so that a 45 degree diagonal emerges on the left most edge of each diagram. Call the new oblique diagrams and . Next reflect across that diagonal and glue it to along that diagonal:
This gives a new partition of size . For instance as above.
- A reverse SSYT(rSSYT) has weakly decreasing rows and strictly decreasing columns (instead of increasing as for SSYT). Given both rSSYT of the same shape, we create a plane partition by doing step 1 as follows: the rth columns of and 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 . Since have the same shape, their columns match up. So this procedure is certainly well-defined.
- Now define from by taking transpose of each row (why this is needed is not clear to me). A fact not proven is that is a bijection between pairs of rSSYTs of the same shape and plane partitions. Obviously
Also . The number of rows in is the maximum among all entries of , and number of columns of is the maximum entry in .
- 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 consists of numbers in the top row, and consists of numbers in the bottom row). To get two rSSYTs and 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 -valued tables and pairs of rSSYT’s in . Note that and . Also . So together with the previous bijection with plane partitions, we get
An additional fact: fix , , let be the number of plane partitions that fit into an box, then
Theorem 3 (MacMahon)
If we impose certain symmetry requirement for the plane partition, the counting problem becomes more interesting (see J. Stembridge, Adv. Math 1995). Think of as an order ideal in . Then acts on it by permutation coordinates. In fact 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 .