
58 Combinatorics of Permutations, Second Edition
PROPOSITION 2.9
The ordinary generating function of the numbers p(n) is
n≥0
p(n)x
n
=
∞
i=1
1
1 − x
i
. (2.2)
PROOF We can decompose the right-hand side as
(1 + x + x
2
+ ···)(1 + x
2
+ x
4
+ ···) ···(1 + x
i
+ x
2i
+ ···).
It is now clear that the coefficient of x
n
in this product is equal to the
number of vectors (c
1
,c
2
, ···) with nonnegative integer coefficients for which
∞
i=1
ic
i
= n. Note that such a vector can have only a finite number of
nonzero coordinates. Finally, there is a natural bijection between these vec-
tors and the partitions of n. This bijection maps (c
1
,c
2
, ···) into the partition
that has c
i
parts equal to ...