TAOCP 5.1.1 Exercise 15
We want to prove that the coefficient of \(z^m\) in \[ \frac{1}{(1-z)(1-z^2)\cdots(1-z^n)} \] equals the number of sequences \((p_1, p_2, \ldots, p_n)\) with \(p_1 \ge p_2 \ge \cdots \ge p_n \ge 0\) a...
Exercise 15. [M25] Prove that (16) is the generating function for partitions into at most $n$ parts; that is, prove that the coefficient of $z^m$ in $1/((1-z)(1-z^2)\ldots(1-z^n))$ is the number of ways to write $m = p_1 + p_2 + \cdots + p_n$ with $p_1 \ge p_2 \ge \cdots \ge p_n \ge 0$. [Hint: Drawing dots as in exercise 14, show that there is a one-to-one correspondence between $n$-tuples $(p_1, p_2, \ldots, p_n)$ such that $p_1 \ge p_2 \ge \cdots \ge p_n \ge 0$ and sequences $(P_1, P_2, P_3, \ldots)$ such that $n \ge P_1 \ge P_2 \ge P_3 \ge \cdots \ge 0$, with the property that $p_1 + p_2 + \cdots + p_n = P_1 + P_2 + P_3 + \cdots$. In other words, partitions into at most $n$ parts correspond to partitions into parts not exceeding $n$.]
Verified: yes
Solve time: 8m12s
Solution
We want to prove that the coefficient of (z^m) in [ \frac{1}{(1-z)(1-z^2)\cdots(1-z^n)} ] equals the number of sequences ((p_1, p_2, \ldots, p_n)) with (p_1 \ge p_2 \ge \cdots \ge p_n \ge 0) and (p_1 + p_2 + \cdots + p_n = m).
First, observe that [ \frac{1}{(1-z)(1-z^2)\cdots(1-z^n)} = \prod_{k=1}^n \frac{1}{1-z^k} = \prod_{k=1}^n \sum_{c_k=0}^\infty z^{k c_k} = \sum_{c_1,\ldots,c_n \ge 0} z^{1\cdot c_1 + 2\cdot c_2 + \cdots + n\cdot c_n}. ] The coefficient of (z^m) is the number of solutions ((c_1,\ldots,c_n) \in \mathbb{Z}{\ge 0}^n) to (\sum{k=1}^n k c_k = m). Each such solution corresponds uniquely to a partition of (m) into parts not exceeding (n), where (c_k) is the multiplicity of part (k). Let us denote such a partition by a sequence ((P_1, P_2, \ldots)) with (n \ge P_1 \ge P_2 \ge \cdots \ge 0) and (\sum_j P_j = m), where the positive (P_j) are the parts listed in nonincreasing order.
Now we establish a bijection between the set (\mathcal{P}_n(m)) of partitions of (m) into at most (n) parts (i.e., sequences ((p_1,\ldots,p_n)) with (p_1 \ge \cdots \ge p_n \ge 0), (\sum p_i = m)) and the set (\mathcal{Q}_n(m)) of partitions of (m) into parts not exceeding (n) (i.e., sequences ((P_1,P_2,\ldots)) with (n \ge P_1 \ge P_2 \ge \cdots \ge 0), (\sum P_j = m)).
Given ((p_1,\ldots,p_n) \in \mathcal{P}n(m)), construct its conjugate partition ((P_1,P_2,\ldots)) by [ P_j = #{ i \mid 1 \le i \le n,; p_i \ge j }, \qquad j = 1,2,\ldots. ] Since (p_1 \ge p_2 \ge \cdots \ge p_n), we have (P_1 \ge P_2 \ge \cdots). Because there are only (n) rows, (P_1 \le n). Also (P_j = 0) for (j > p_1). The total number of dots is preserved: [ \sum{i=1}^n p_i = \sum_{i=1}^n \sum_{j=1}^{p_i} 1 = \sum_{j=1}^\infty \sum_{i=1}^n [p_i \ge j] = \sum_{j=1}^\infty P_j. ] Thus ((P_1,P_2,\ldots) \in \mathcal{Q}_n(m)).
Conversely, given ((P_1,P_2,\ldots) \in \mathcal{Q}_n(m)), define [ p_i = #{ j \mid P_j \ge i }, \qquad i = 1,\ldots,n. ] Since (P_1 \ge P_2 \ge \cdots), we have (p_1 \ge p_2 \ge \cdots \ge p_n \ge 0). Because (P_1 \le n), we have (p_i = 0) for (i > n) (but we only define up to (n)). The sums are equal by the same double-counting argument. This mapping is clearly the inverse of the previous one.
Therefore (|\mathcal{P}_n(m)| = |\mathcal{Q}_n(m)|) for every (m). Since the generating function of (\mathcal{Q}n(m)) is exactly (\prod{k=1}^n 1/(1-z^k)), the coefficient of (z^m) in that product is (|\mathcal{P}_n(m)|), the number of partitions of (m) into at most (n) parts. This completes the proof.
∎