3.4: Partitions of Integers
( \newcommand{\kernel}{\mathrm{null}\,}\)
A partition of a positive integer n is a multiset of positive integers that sum to n. We denote the number of partitions of n by pn.
Typically a partition is written as a sum, not explicitly as a multiset. Using the usual convention that an empty sum is 0, we say that p0=1.
The partitions of 5 are 54+13+23+1+12+2+12+1+1+11+1+1+1+1. Thus p5=7.
There is no simple formula for pn, but it is not hard to find a generating function for them. As with some previous examples, we seek a product of factors so that when the factors are multiplied out, the coefficient of xn is pn. We would like each xn term to represent a single partition, before like terms are collected. A partition is uniquely described by the number of 1s, number of 2s, and so on, that is, by the repetition numbers of the multiset. We devote one factor to each integer: (1+x+x2+x3+⋯)(1+x2+x4+x6+⋯)⋯(1+xk+x2k+x3k+⋯)⋯=∞∏k=1∞∑i=0xik. When this product is expanded, we pick one term from each factor in all possible ways, with the further condition that we only pick a finite number of "non-1'' terms. For example, if we pick x3 from the first factor, x3 from the third factor, x15 from the fifth factor, and 1s from all other factors, we get x21. In the context of the product, this represents 3⋅1+1⋅3+3⋅5, corresponding to the partition 1+1+1+3+5+5+5, that is, three 1s, one 3, and three 5s. Each factor is a geometric series; the kth factor is 1+xk+(xk)2+(xk)3+⋯=11−xk, so the generating function can be written ∞∏k=111−xk. Note that if we are interested in some particular pn, we do not need the entire infinite product, or even any complete factor, since no partition of n can use any integer greater than n, and also cannot use more than n/k copies of k.
Find p8.
Solution
We expand
(1+x+x2+x3+x4+x5+x6+x7+x8)(1+x2+x4+x6+x8)(1+x3+x6)(1+x4+x8)(1+x5)(1+x6)(1+x7)(1+x8)=1+x+2x2+3x3+5x4+7x5+11x6+15x7+22x8+⋯+x56,
so p8=22. Note that all of the coefficients prior to this are also correct, but the following coefficients are not necessarily the corresponding partition numbers. Here is how to use Sage for the computation. We define f=∏8k=111−xk to make sure the x8 coefficient will be correct. Instead of doing the explicit product above, we use Sage to compute the Taylor series, which has the same effect.
1 | f = prod([ 1 / ( 1 - x^k) for k in range ( 1 , 9 )]); f; f.taylor(x, 0 , 8 ) |
Partitions of integers have some interesting properties. Let pd(n) be the number of partitions of n into distinct parts; let po(n) be the number of partitions into odd parts.
For n=6, the partitions into distinct parts are 6,5+1,4+2,3+2+1, so pd(6)=4, and the partitions into odd parts are 5+1,3+3,3+1+1+1,1+1+1+1+1+1, so po(6)=4.
In fact, for every n, pd(n)=po(n), and we can see this by manipulating generating functions. The generating function for pd(n) is fd(x)=(1+x)(1+x2)(1+x3)⋯=∞∏i=1(1+xi). The generating function for po(n) is fo(x)=(1+x+x2+x3+⋯)(1+x3+x6+x9+⋯)⋯=∞∏i=011−x2i+1. We can write fd(x)=1−x21−x⋅1−x41−x2⋅1−x61−x3⋯ and notice that every numerator is eventually canceled by a denominator, leaving only the denominators containing odd powers of x, so fd(x)=fo(x).
We can also use a recurrence relation to find the partition numbers, though in a somewhat less direct way than the binomial coefficients or the Bell numbers. Let pk(n) be the number of partitions of n into exactly k parts. We will find a recurrence relation to compute the pk(n), and then pn=n∑k=1pk(n). Now consider the partitions of n into k parts. Some of these partitions contain no 1s, like 3+3+4+6, a partition of 16 into 4 parts. Subtracting 1 from each part, we get a partition of n−k into k parts; for the example, this is 2+2+3+5. The remaining partitions of n into k parts contain a 1. If we remove the 1, we are left with a partition of n−1 into k−1 parts. This gives us a 1–1 correspondence between the partitions of n into k parts, and the partitions of n−k into k parts together with the partitions of n−1 into k−1 parts, so pk(n)=pk(n−k)+pk−1(n−1).
Using this recurrence we can build a triangle containing the pk(n), and the row sums of this triangle give the partition numbers. For all n, p1(n)=1, which gives the first column of the triangle, after which the recurrence applies. Also, note that pk(n)=0 when k>n and we let pk(0)=0; these are needed in some cases to compute the pk(n−k) term of the recurrence. Here are the first few rows of the triangle; at the left are the row numbers, and at the right are the row sums, that is, the partition numbers. For the last row, each entry is the sum of the like-colored numbers in the previous rows. Note that beginning with p4(7)=3 in the last row, pk(7)=pk−1(6), as pk(7−k)=0.
11121123111341211551221176133211117134321115
Yet another sometimes useful way to think of a partition is with a Ferrers diagram. Each integer in the partition is represented by a row of dots, and the rows are ordered from longest on the top to shortest at the bottom. For example, the partition 3+3+4+5 would be represented by

The conjugate of a partition is the one corresponding to the Ferrers diagram produced by flipping the diagram for the original partition across the main diagonal, thus turning rows into columns and vice versa. For the diagram above, the conjugate is

with corresponding partition 1+2+4+4+4. This concept can occasionally make facts about partitions easier to see than otherwise. Here is a classic example: the number of partitions of n with largest part k is the same as the number of partitions into k parts, pk(n). The action of conjugation takes every partition of one type into a partition of the other: the conjugate of a partition into k parts is a partition with largest part k and vice versa. This establishes a 1–1 correspondence between partitions into k parts and partitions with largest part k.