<<

. 2
( 14 .)



>>

(1 ’ x)(1 ’ x2 )(1 ’ x3 ) · · ·
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 .

<<

. 2
( 14 .)



>>