8.5: Partitions of an Integer

A recurring theme in this course has been to count the number of integer solutions to an equation of the form \(x_1+x_2+ \cdot \cdot \cdot +x_k=n\). What if we wanted to count the number of such solutions but didn't care what \(k\) was? How about if we took this new question and required that the \(x_i\) be distinct (i.e., \(x_i \neq x_j\) for \(i \neq j\))? What about if we required that each \(x_i\) be odd? These certainly don't seem like easy questions to answer at first, but generating functions will allow us to say something very interesting about the answers to the last two questions.

By a partition \(P\) of an integer, we mean a collection of (not necessarily distinct) positive integers such that \(\sum_{i \in P} i =n\). (By convention, we will write the elements of \(P\) from largest to smallest.) For example, 2+2+1 is a partition of 5. For each \(n \geq 0\), let pn denote the number of partitions of the integer \(n\) (with \(p_0=1\) by convention). Note that \(p_8=22\) as evidenced by the list in Figure 8.15.

Figure 8.15. The partitions of 8, noting those into distinct parts and those into odd parts.

Note that there are 6 partitions of 8 into distinct parts. Also there are 6 partitions of 8 into odd parts. While it might seem that this is a coincidence, it in fact is always the case as Theorem 8.16 states. Before looking at that theorem and its proof, let's think about what a generating function for \(p_n\), the number of partitions of \(n\), would look like. Given a partition of \(n\), we can count how many 1's appear, how many 2's appear, and so on. This suggests a similarity with our fruit basket problems earlier in the chapter, leading to the generating function

\(P(x) = ( \displaystyle \sum_{m=0}^{\infty} x^m ) (\sum_{m=0}^{\infty}x^{2m})(\sum_{m=0}^{\infty}x^{3m}) \cdot \cdot \cdot (\sum_{m=0}^{\infty} x^{km}) \cdot \cdot \cdot = \prod_{m=1}^{\infty} \dfrac{1}{1-x^m}\).

Here the factor whose sum contains terms \(x^{km}\) is accounting for the number of \(k\)'s in the partition. While \(P(x)\) has a quite elegant form, that doesn't mean that it's terribly useful for computing \(p_n\). In fact, providing an asymptotic estimate for \(p_n\) was a notoriously difficult problem, finally addressed by Hardy and Ramanujan in 1918. A popular account of this can be found in Robert Kanigel's 1991 book The Man who Knew Infinity or the 2016 film with the same title.

Proving the relationship between the number of partitions into distinct parts and the number of partitions into odd parts will involve restricted versions of the generating function \(P(x)\) from above.

Theorem 8.16

For each \(n \geq 1\), the number of partitions of \(n\) into distinct parts is equal to the number of partitions of \(n\) into odd parts.

Proof

The generating function \(D(x)\) for the number of partitions of \(n\) into distinct parts is

\(D(x) = \displaystyle \prod_{n=1}^{\infty}(1 + x^n)\).

On the other hand, the generating function \(O(x)\) for the number of partitions of \(n\) into odd parts is

\(O(x) = \displaystyle \prod_{n=1}^{\infty} \dfrac{1}{1-x^{2n-1}}\).

To see that \(D(x)=O(x)\), we note that \(1−x^{2n}=(1−x^n)(1+x^n)\) for all \(n \geq 1\). Therefore,

\(D(x) = \displaystyle \prod_{n=1}^{\infty}(1+x^n) = \prod_{n=1}^{\infty} \dfrac{1-x^{2n}}{1-x^n} = \dfrac{\prod_{n=1}^{\infty}(1-x^{2n})}{\prod_{n=1}^{\infty}(1-x^n)}\)

\(= \dfrac{\prod_{n=1}^{\infty}(1-x^{2n})}{\prod_{n=1}^{\infty}(1-x^{2n-1}) \prod_{n=1}^{\infty}(1-x^{2n})} = \displaystyle \prod_{n=1}^{\infty} \dfrac{1}{1-x^{2n-1}}\)

\(= O(x)\)