TAOCP 1.2.9 Exercise 8
Let $p(n)$ denote the number of partitions of $n$, with $p(0)=1$.
Section 1.2.9: Generating Functions
Exercise 8. [M23] Find the generating function for $p(n)$, the number of partitions of $n$.
Verified: yes
Solve time: 4m23s
Solution
Let $p(n)$ denote the number of partitions of $n$, with $p(0)=1$.
For each integer $k \ge 1$, the geometric series (5) with $z$ replaced by $z^k$ gives
$$ \frac{1}{1-z^k} = 1 + z^k + z^{2k} + \cdots = \sum_{j \ge 0} z^{kj}. $$
Consider the infinite product
$$ P(z) = \prod_{k \ge 1} \frac{1}{1-z^k} = \prod_{k \ge 1} \left(\sum_{j_k \ge 0} z^{k j_k}\right). $$
Expanding the product using repeated application of the multiplication rule (9), each term in the expansion is obtained by selecting, for every $k \ge 1$, a nonnegative integer $j_k$ and contributing the factor $z^{k j_k}$. The resulting term is
$$ z^{\sum_{k \ge 1} k j_k}. $$
Hence the coefficient of $z^n$ in $P(z)$ equals the number of sequences $(j_1,j_2,j_3,\ldots)$ of nonnegative integers satisfying
$$ \sum_{k \ge 1} k j_k = n. $$
Each such sequence corresponds uniquely to a partition of $n$ in which the part $k$ occurs exactly $j_k$ times, and every partition determines such a sequence by counting multiplicities of each part size. This establishes a bijection between partitions of $n$ and solutions of the stated equation.
Therefore the coefficient of $z^n$ in $P(z)$ is $p(n)$, and the generating function for $\langle p(n)\rangle$ is
$$ \sum_{n \ge 0} p(n) z^n = \prod_{k \ge 1} \frac{1}{1-z^k}. $$
This completes the proof. ∎
$$ \boxed{\sum_{n \ge 0} p(n) z^n = \prod_{k \ge 1} \frac{1}{1-z^k}} $$