Although equation (3) is very elegant, one may ask whether it is of any

use. Can it be used to obtain interesting information about the numbers

p(n)? We will ¬rst show how simple manipulation of generating functions

(due to Euler) gives a surprising connection between two types of partitions.

Let r(n) be the number of partitions of n into odd parts. For instance,

r(7) = 5, the relevant partitions being

7 = 5 + 1 + 1 = 3 + 3 + 1 = 3 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 + 1 + 1.

Let

R(x) = r(0) + r(1)x + r(2)x2 + r(3)x3 + · · · .

7

Exactly as equation (3) was obtained we get

1

R(x) = . (4)

(1 ’ x)(1 ’ x3 )(1 ’ x5 )(1 ’ x7 ) · · ·

Similarly, let q(n) be the number of partitions of n into distinct parts, that

is, no integer can occur more than once as a part. For instance, q(7) = 5,

the relevant partitions being

7 = 6 + 1 = 5 + 2 = 4 + 3 = 4 + 2 + 1.

Note that r(7) = q(7). In order to explain this “coincidence,” let

Q(x) = q(0) + q(1)x + q(2)x2 + q(3)x3 + · · · .

The reader who understands the derivation of equation (3) will have no trou-

ble seeing that

Q(x) = (1 + x)(1 + x2 )(1 + x3 ) · · · . (5)

Now we come to the ingenious trick of Euler. Note that by ordinary “high

school algebra,” we have

1 ’ x2n

n

1+x = .

1 ’ xn

Thus from equation (5) we obtain

1 ’ x2 1 ’ x4 1 ’ x6

Q(x) = · · ···

1 ’ x 1 ’ x2 1 ’ x3

(1 ’ x2 )(1 ’ x4 )(1 ’ x6 )(1 ’ x8 ) · · ·

= . (6)

(1 ’ x)(1 ’ x2 )(1 ’ x3 )(1 ’ x4 ) · · ·

When we cancel the factors 1’x2i from both the numerator and denominator,

we are left with

1

Q(x) = ,

(1 ’ x)(1 ’ x3 )(1 ’ x5 ) · · ·

which is just the product formula (4) for R(x). This means that Q(x) = R(x).

Thus the coe¬cients of Q(x) and R(x) are the same, so we have proved that

q(n) = r(n) for all n. In other words, for every n the number of partitions

of n into distinct parts equals the number of partitions of n into odd parts.

8

The above argument shows the usefulness of working with generating

functions. Many similar generating function techniques have been developed

that make generating functions into a fundamental tool of enumerative com-

binatorics.

Once we obtain a formula such as q(n) = r(n) by an indirect means like

generating functions, it is natural to ask whether there might be a simpler

proof. For the problem at hand, we would like to correspond to each partition

of n into distinct parts a partition of n into odd parts, such that every

partition of n into odd parts is associated with exactly one partition of n

into distinct parts, and conversely every partition of n into distinct parts is

associated with exactly one partition of n into odd parts. In other words, we

want a one-to-one correspondence or bijection between the partitions of n into

odd parts and the partitions of n into distinct parts. Such a bijection would

yield a bijective proof of the formula q(n) = r(n). Exhibiting a bijection

between two di¬erent (¬nite) sets is considered the most elegant and natural

way to show that they have the same number of elements. Such bijective

proofs can involve considerable ingenuity, while the method of generating

functions often yields a more mechanical proof technique.

We now would like to give a bijective proof of Euler™s formula q(n) = r(n).

Several such proofs are known; we give the perhaps simplest of these, due

to James Joseph Sylvester (1814“1897). It is based on the fact that every

positive integer n can be uniquely written as a sum of distinct powers of

two ” this is simply the binary expansion of n. For instance, 10000 =

213 + 210 + 29 + 28 + 24 . Suppose we are given a partition into odd parts, such

as

202 = 19 + 19 + 19 + 11 + 11 + 11 + 11 + 9 + 7 + 7 + 7 + 5

+5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 1 + 1 + 1 + 1 + 1 + 1.

We can rewrite this partition as

3 · 19 + 4 · 11 + 1 · 9 + 3 · 7 + 13 · 5 + 6 · 1,

where each part is multiplied by the number of times it appears. This is just

the expression m1 + 2m2 + 3m3 + · · · for a partition discussed above. Now

write each of the numbers mi as a sum of distinct powers of 2. For the above

example, we get

202 = (2 + 1) · 19 + 4 · 11 + 1 · 9 + (2 + 1) · 7 + (8 + 4 + 1) · 5 + (4 + 2) · 1.

9

Expand each product into a sum (by the distributivity of multiplication over

addition):

202 = (38 + 19) + 44 + 9 + (14 + 7) + (40 + 20 + 5) + (4 + 2). (7)

We have produced a partition of the same number n with distinct parts.

That the parts are distinct is a consequence of the fact that every integer n

can be uniquely written as the product of an odd number and a power of 2

(keep on dividing n by 2 until an odd number remains). Moreover, the whole

procedure can be reversed. That is, given a partition into distinct parts such

as

202 = 44 + 40 + 38 + 20 + 19 + 14 + 9 + 7 + 5 + 4 + 2,

group the terms together according to their largest odd divisor. For instance,

40, 20, and 5 have the largest odd divisor 5, so we group them together. We

thus recover the grouping (7). We can now factor the largest odd divisor d out

of each group, and what remains is the number of times d appears as a part.

Thus we have recovered the original partition. This reasoning shows that we

have indeed produced a bijection between partitions of n into odd parts and

partitions of n into distinct parts. It provides a “natural” explanation of the

fact that q(n) = r(n), unlike the generating function proof which depended

on a miraculous trick.

The subject of partitions is replete with results similar to Euler™s, in which

two sets of partitions have the same number of elements. The most famous of

these results is called the Rogers-Ramanujan identities, after Leonard James

Rogers (1862“1933) and Srinivasa Aiyangar Ramanujan (1887“1920), who

proved these identities in the form of an identity between generating func-

tions. It was Percy Alexander MacMahon (1854“1929) who interpreted them

combinatorially as follows.

First Rogers-Ramanujan Identity. Let f (n) be the number of par-

titions of n whose parts di¬er by at least 2. For instance, f (13) = 10, the

relevant partitions being

13 = 12 + 1 = 11 + 2 = 10 + 3 = 9 + 4 = 8 + 5 = 9 + 3 + 1

= 8 + 4 + 1 = 7 + 5 + 1 = 7 + 4 + 2.

10

Similarly, let g(n) be the number of partitions of n whose parts are of the

form 5k + 1 or 5k + 4 (i.e., leave a remainder of 1 or 4 upon division by 5).

For instance, g(13) = 10:

11 + 1 + 1 = 9 + 4 = 9 + 1 + 1 + 1 + 1 = 6 + 6 + 1 = 6 + 4 + 1 + 1 + 1

= 6+1+1+1+1+1+1+1 = 4+4+4+1 = 4+4+1+1+1+1+1

= 4+1+1+1+1+1+1+1+1+1 = 1+1+1+1+1+1+1+1+1+1+1+1+1.

Then f (n) = g(n) for every n.

Second Rogers-Ramanujan Identity. Let u(n) be the number of par-

titions of n whose parts di¬er by at least 2 and such that 1 is not a part. For

instance, u(13) = 6, the relevant partitions being

13 = 11 + 2 = 10 + 3 = 9 + 4 = 8 + 5 = 7 + 4 + 2.

Similarly, let v(n) be the number of partitions of n whose parts are of the

form 5k + 2 or 5k + 3 (i.e., leave a remainder of 2 or 3 upon division by 5).

For instance, v(13) = 6:

13 = 8+3+2 = 7+3+3 = 7+2+2+2 = 3+3+3+2+2 = 3+2+2+2+2+2.

Then u(n) = v(n) for every n.

The Rogers-Ramanujan identities have been given many proofs, but none

of them is really easy. The important role played by the number 5 seems

particularly mysterious. For a long time it was an open problem to ¬nd

a bijective proof of the Rogers-Ramanujan identities, but such a proof was

¬nally given in 1980 by Adriano M. Garsia (b. 1928) and Stephen Carl Milne

(b. 1949). However, their proof is very complicated, and it would still be of

great interest to ¬nd a simple, conceptual bijective proof.

The Rogers-Ramanujan identities and related identities are not just num-

ber-theoretic curiosities. They have arisen completely independently in sev-

eral seemingly unrelated areas. To give just one example, a famous open

problem in statistical mechanics, known as the hard hexagon model, was

solved in 1980 by Rodney James Baxter (b. 1940) using the Rogers-Ramanujan

identities.

11

7 4 4 4 2 21111

7 4 4 2 2 1111

6 3 2 2 2 1111

4 2 2 1 1 1

2 2 1 1 1

2 1 1 1 1

1 1 1 1 1

1 1

Figure 1: A plane partition

3 Plane partitions.

A partition such as 8 + 6 + 6 + 5 + 2 + 2 + 2 + 2 + 1 + 1 may be regarded

simply as a linear array of positive integers,

8665222211

whose entries are weakly decreasing, i.e., each entry is greater than or equal

to the one on its right. Viewed in this way, one can ask if there are interesting

“multidimensional” generalizations of partitions, in which the parts don™t lie

on just a line, but rather on some higher dimensional object. The simplest

generalization occurs when the parts lie in a plane. Rather than having the

parts weakly decreasing in a single line, we now want the parts to be weakly

decreasing in every row and column. More precisely, let » be a partition with

its parts »1 , »2 , . . . , » written in weakly decreasing order, so »1 ≥ »2 ≥ · · · ≥

» > 0. We de¬ne a plane partition π of shape » to be a left-justi¬ed array

of positive integers (called the parts of π) such that (1) there are »i parts in

the ith row, and (2) every row (read left-to-right) and column (read top-to-

bottom) is weakly decreasing. An example of a plane partition is given in

Figure 1.

We say that π is a plane partition of n if n is the sum of the parts of

π. Thus the plane partition of Figure 1 is a plane partition of 100, of shape

12

(10, 9, 9, 6, 5, 5, 5, 2). It is clear what is meant by the number of rows and

number of columns of π. For the example in Figure 1, the number of rows is

8 and the number of columns is 10. The plane partitions of integers up to 3

(including the empty set ˜, which is regarded as a plane partition of 0) are

given by

˜ 1 2 11 1 3 21 111 11 2 1

1 1 1 1.

1

Thus, for instance, there are six plane partitions of 3.

In 1912 MacMahon began a study of the theory of plane partitions.

MacMahon was a mathematician well ahead of his time. He worked in virtual

isolation on a variety of topics within enumerative combinatorics that did not

become fashionable until many years later. A highlight of MacMahon™s work

was a simple generating function for the number of plane partitions of n.

More precisely, let pp(n) denotes the number of plane partitions of n, so

that pp(0) = 1, pp(1) = 1, pp(2) = 3, pp(3) = 6, pp(4) = 13, etc. Then

MacMahon established the remarkable formula

pp(0) + pp(1)x + pp(2)x2 + pp(3)x3 + · · ·

1

= . (8)

(1 ’ x)(1 ’ x2 )2 (1 ’ x3 )3 (1 ’ x4 )4 · · ·

Unlike Euler™s formula (3) for the generating function for the number p(n) of

ordinary partitions of n, MacMahon™s formula is by no means easy to prove.

MacMahon™s proof was an intricate induction argument involving manip-

ulations of determinants. Only much later was a bijective proof found by

Edward Anton Bender (b. 1942) and Donald Ervin Knuth (b. 1938). Their

proof was based on the Schensted correspondence, a central result in enu-

merative combinatorics and its connections with the branch of mathematics

known as representation theory. This correspondence was ¬rst stated by

Gilbert de Beauregard Robinson (1906“19??) in a rather vague form in 1938

(with some assistance from Dudley Ernest Littlewood (1903“1979)), and later

more explicitly by Craige Eugene Schensted (b. 19??) in 1961. Schensted™s

motivation for looking at this correspondence is discussed in Section 5. The

version of Schensted™s correspondence used here is due to Knuth.

13

We now give a brief account of the proof of Bender and Knuth. Using

equation (1), the product on the right-hand side of (8) may be written

1

= (1 + x + x2 + · · ·)(1 + x2 + x4 + · · ·)

2 )2 (1 ’ x3 )3 (1 ’ x4 )4 · · ·

(1 ’ x)(1 ’ x

(1+x2 +x4 +· · ·)(1+x3 +x6 +· · ·)(1+x3 +x6 +· · ·)(1+x3 +x6 +· · ·) · · · . (9)

In general, there will be k factors of the form 1 + xk + x2k + x3k + · · ·. We

must pick a term out of each factor (with only ¬nitely many terms not equal

to 1) and multiply them together to get a term xn of the product. A bijective

proof of (8) therefore consists of associating a plane partition of n with each

choice of terms from the factors 1 + xk + x2k + · · ·, such that the product of

these terms is xn .