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