<<

. 3
( 14 .)



>>

Our ¬rst step is to encode a choice of terms from each factor by an array
of numbers called a two-line arry. A typical two-line array A looks like
3332222211111
A= . (10)
3112221144333

The ¬rst line is a (¬nite) weakly decreasing sequence of positive integers.
The second line consists of a positive integer below each entry in the ¬rst
line, such that the integers in the second line appearing below equal integers
in the ¬rst line are in weakly decreasing order. For instance, for the two-
line array A above, the integers appearing below the 2™s of the ¬rst line are
2 2 2 1 1 (in that order). Such a two-line array encodes a choice of terms
from the factors of the product (9) as follows. Let aij be the number of
i
columns j of A. For instance (always referring to the two-line array (10)),
a33 = 1, a31 = 2, a13 = 3, a23 = 0. Given aij , let k = i + j ’ 1. Then choose
the term xaij ·k from the ith factor of (9) of the form 1 + xk + x2k + · · ·. For
instance, since a33 = 1 we have k = 5 and choose the term x1·5 = x5 from the
third factor of the form 1 + x5 + x10 + · · ·. Since a31 = 2 we have k = 3 and
choose the term x2·3 = x6 from the third factor of the form 1 + x3 + x6 + · · ·,
etc. In this way we obtain a one-to-one correspondence between a choice of
terms from each factor of the product (9) (with only ¬nitely terms not equal
to 1) and two-line arrays A.

We now describe the part of the Bender-Knuth bijection which is the
Schensted correspondence. It will be described as an algorithm that we call

14
the Schensted algorithm. We will insert the numbers in each line of the two-
line array A into a successively evolving plane partition, yielding in fact a
pair of plane partitions. These plane partitions will have the special property
of being column-strict, that is, the (nonzero) entries are strictly decreasing
in each column. Thus after we have inserted the ¬rst i numbers of the ¬rst
and second lines of A, we will have a pair Pi and Qi of column-strict plane
partitions. We insert the numbers of the second line of A successively from
left-to-right by the following rule. Assuming that we have inserted the ¬rst
i ’ 1 numbers, yielding Pi’1 and Qi’1 , we insert the ith number a of the
second row of A into Pi’1 , by putting it as far to the right as possible in the
¬rst row of Pi’1 so that this row remains weakly decreasing. In doing so,
it may displace (or bump) another number b already in the ¬rst row. Then
insert b into the second row according to the same rule, that is, as far to the
right as possible so that the second row remains weakly decreasing. Then
b may bump a number c into the third row, etc. Continue this “bumping
procedure” until ¬nally a number is inserted at the end of the row, thereby
not bumping another number. This yields the column-strict plane partition
Pi . (It takes a little work, which we omit, to show that Pi is indeed column-
strict.) Now insert the ith number of the ¬rst row of A (that is, the number
just above a in A) into Qi’1 to form Qi , by placing it so that Pi and Qi
have the same shape, that is, the same number of elements in each row. If
A has m columns, then the process stops after obtaining Pm and Qm , which
we denote simply as P and Q.

Example. Figure 2 illustrates the bumping procedure with the two-line
array A of equation (10). For instance, to obtain P10 from P9 we insert 4
into the ¬rst row of P9 . The 4 is inserted into the second column and bumps
the 2 into the second row. The 2 is also inserted into the second column and
bumps the 1 into the third row. The 1 is placed at the end of the third row.
To obtain Q10 from Q9 we must place 1 so that P10 and Q10 have the same
shape. Hence 1 is placed at the end of the third row. From the bottom entry
(i = 13) of Figure 2 we obtain:

443331 333222
P = 32221 , Q = 22111 . (11)
11 11


The ¬nal step of the Bender-Knuth bijection is to merge the two column-

15
i Pi Qi
13 3
2 31 33
3 311 333
4 321 333
1 2
5 322 333
11 22
6 3222 3332
11 22
7 32221 33322
11 22
8 322211 333222
11 22
9 422211 333222
31 22
1 1
10 4 4 2 2 1 1 3 3 3 2 2 2
32 22
11 11
11 4 4 3 2 1 1 3 3 3 2 2 2
322 221
11 11
12 4 4 3 3 1 1 3 3 3 2 2 2
3222 2211
11 11
13 4 4 3 3 3 1 3 3 3 2 2 2
32221 22111
11 11

Figure 2: The Schensted correspondence




16
strict plane partitions P and Q into a single plane partition π. We do this by
merging column-by-column, that is, the kth columns of P and Q are merged
to form the kth column of π. Let us ¬rst merge the ¬rst columns of P and Q
in equation (11). The following diagram illustrates the merging procedure:

r r r r
@
@
r @r r r
@
@
r r @r


The number of dots in each row on or to the right of the main diagonal
(which runs southeast from the upper left-hand corner) is equal to 4, 3, 1,
the entries of the ¬rst column of P . Similarly, the number of dots in each
column on or below the main diagonal is equal to 3, 2, 1, the entries of the
¬rst column of Q. The total number of dots in each row is 4, 4, 3, and we let
these numbers be the entries of the ¬rst column of π. In the same way, the
second column of π has entries 4, 3, 3, as shown by the following diagram:
r r r r
@
@
r @r r
@
@
r r @r


When this merging procedure is carried out to all the columns of P and
Q, we obtain the plane partition

443331
π = 433321 . (12)
331

This gives the desired bijection that proves MacMahon™s formula (8). Of
course there are many details to be proved in order to verify that this pro-
cedure has all the necessary properties. The key point is that every step is
reversible. A good way to convince yourself of the accuracy of the procedure
is to take the plane partition π of equation (12) and try to reconstruct the
original choice of terms from the product 1/(1 ’ x)(1 ’ x2 )2 · · ·.

17
By analyzing more carefully the above bijective proof, it is possible to
extend the formula (8) of MacMahon. Write [i] as short for 1 ’ xi . Without
going into any of the details, let us simply state that if pprs (n) denotes the
number of plane partitions of n with at most r rows and at most s columns,
where say r ¤ s, then

1 + pprs (1)x + pprs (2)x2 + · · · =
1
. (13)
[1][2]2 [3]3 · · · [r]r [r + 1]r · · · [s]r [s + 1]r’1 [s + 2]r’2 · · · [r + s ’ 1]
For instance, when r = 3 and s = 5 the right-hand side of equation (13)
becomes
1
(1 ’ x)(1 ’ x2 )2 (1 ’ x3 )3 (1 ’ x4 )3 (1 ’ x5 )3 (1 ’ x6 )2 (1 ’ x7 )

= 1+x+3x2 +6x3 +12x4 +21x5 +39x6 +64x7 +109x8 +175x9 +280x10 +· · · .
For example, the fact that the coe¬cient of x4 is 12 means that there are
12 plane partitions of 4 with at most 3 rows and at most 5 columns. These
plane partitions are given by

4 31 22 211 1111 3 2 21 11 111 2 11
1 2 1 11 1 1 1.
1 1

By more sophisticated arguments (not a direct bijective proof) one can extend
equation (13) even further, as follows. Let pprst (n) denote the number of
plane partitions of n with at most r rows, at most s columns, and with
largest part at most t. Then

1 + pprst (1)x + pprst (2)x2 + · · · =

[1 + t][2 + t]2 [3 + t]3 · · · [r + t]r [r + 1 + t]r · · · [s + t]r [s + 1 + t]r’1 [s + 2 + t]r’2 · · · [r + s ’ 1 + t]
.
[1][2]2 [3]3 · · · [r]r [r + 1]r · · · [s]r [s + 1]r’1 [s + 2]r’2 · · · [r + s ’ 1]
(14)

Note that the right-hand sides of equations (13) and (14) have the same
denominator. The numerator of (14) is obtained by replacing each denomi-
nator factor [i] with [i+t]. Equation (14) was also ¬rst proved by MacMahon,
and is the culmination of his work on plane partitions. It is also closely related

18
to the representation theory of Lie groups and Lie algebras, a subject that at
¬rst sight has no connection with plane partitions. (See Box.) MacMahon™s
results have many other variations which give simple product formulas for
enumerating various classes of plane partitions. It seems natural to try to
extend these results to even higher dimensions. Thus a three-dimensional
analogue of plane partitions would be solid partitions. All attempts (be-
ginning in fact with MacMahon) to ¬nd nice formulas for general classes of
solid partitions have resulted in failure. It seems that plane partitions are
fundamentally di¬erent in behavior than their higher dimensional analogues.

As a concrete example of equation (14), suppose that r = 2, s = 3, and
t = 2. The right-hand side of (14) becomes

(1 ’ x3 )(1 ’ x4 )2 (1 ’ x5 )2 (1 ’ x6 )
(1 ’ x)(1 ’ x2 )2 (1 ’ x3 )2 (1 ’ x4 )

= 1 + x + 3x2 + 4x3 + 6x4 + 6x5 + 8x6 + 6x7 + 6x8 + 4x9 + 3x10 + x11 + x12 .

The Schensted correspondence has a number of remarkable properties
that were not needed for the derivation of MacMahon™s formula (8). The
most striking of these properties is the following. Consider a two-line array
A such as (10) which is the input to the Schensted correspondence. Now
interchange the two rows, and sort the columns so that the ¬rst row is weakly
decreasing, and the part of the second row below a ¬xed number in the ¬rst
row is also weakly decreasing. Call this new two-line array the transposed
array A . For the two-line array A of equation (10) we have

4433332221111
A= (15)
1131112223322

Thus the Schensted correspondence can be applied to A . If (P, Q) is the
pair of column-strict plane partitions obtained by applying the Schensted
correspondence to A, then applying this correspondence to A produces the
pair (Q, P ), that is, the roles of P and Q are reversed! Keeping in mind the
totally di¬erent combinatorial rules for forming P and Q, it seems almost
miraculous when trying a particular example such as (10) and (15) that
we obtain such a simple result. We can use this “symmetry property” of the
Schensted correspondence to enumerate further classes of plane partitions. In

19
particular, a plane partition is called symmetric if it remains the same when
re¬‚ected about the main diagonal running from the upper left-hand corner in
the southeast direction. An example of a symmetric plane partition is given
by
5332111
33321
33211
221
111
1
1
Let s(n) denote the number of symmetric plane partitions of n. For instance,
s(5) = 4, as shown by
5 31 21 111
1 11 1 .
1
Without going into any details, let us just say that the symmetry property of
the Schensted correspondence just described yields a bijective proof, similar
to the proof we have given of MacMahon™s formula (8), of the generating
function
s(0) + s(1)x + s(2)x2 + · · ·
1
= .
(1 ’ x)(1 ’ x3 )(1 ’ x4 )(1 ’ x5 )(1 ’ x6 )(1 ’ x7 )(1 ’ x8 )2 (1 ’ x9 )(1 ’ x10 )2 · · ·
The exponent of 1’x2k’1 in the denominator is 1, and the exponent of 1’x2k
is k/2 , the greatest integer less than or equal to k/2.



4 Standard Young tableaux.

There is a special class of objects closely related to plane partitions that
are of considerable interest. Let » be an ordinary partition of n with parts
»1 ≥ »2 ≥ · · · ≥ » . A standard Young tableau (SYT) of shape » is a left-
justi¬ed array of positive integers, with »i integers in the ith row, satisfying
the following two conditions: (1) The entries consist of the integers 1, 2, ..., n,
each occurring exactly once, and (2) the entries in each row and column are

<<

. 3
( 14 .)



>>