TAOCP 7.2.1.4 Exercise 16
A partition of $n$ has **trace $k$** when its Ferrers diagram has Durfee square of size $k$.
Section 7.2.1.4: Generating All Partitions
Exercise 16. [M21] [M21] Find a formula for m,n p(k, m, n)wmzn, where p(k, m, n) is the number of partitions of n that have m parts and trace k. Sum it on k to obtain a nontrivial identity.
7.2.1.4 GENERATING ALL PARTITIONS 409
Verified: no
Solve time: 6m39s
Solution
A partition of $n$ has trace $k$ when its Ferrers diagram has Durfee square of size $k$. This means the diagram contains a $k \times k$ square, and no larger square fits. Equivalently, exactly $k$ parts are at least $k$, and exactly $k$ parts of the conjugate partition are at least $k$.
Let a partition with trace $k$ be decomposed around its Durfee square. The Ferrers diagram splits into three disjoint regions: the $k \times k$ square, a region to the right of the square inside the first $k$ rows, and a region below the square inside the first $k$ columns.
Let the right-hand region be encoded by a partition $\alpha$ whose parts are the row-wise excesses
$$ \alpha_i = a_i - k \quad (1 \le i \le k), $$
so $\alpha$ has at most $k$ parts and contributes total size $|\alpha| = \sum_{i=1}^k (a_i - k)$. Let the lower region be encoded, after conjugation, by a partition $\beta$ with at most $k$ parts, where each part records how many cells lie below the Durfee square in each column; its size is $|\beta|$. The total size of the original partition is therefore
$$ n = k^2 + |\alpha| + |\beta|. $$
The number of parts of the original partition equals the number of rows, which is $k$ (from the Durfee square) plus the number of additional rows contributed by the lower region. These additional rows are exactly the parts of $\beta$, hence
$$ m = k + \ell(\beta), $$
where $\ell(\beta)$ is the number of parts of $\beta$.
Generating functions for the two components
Partitions with parts bounded by $k$ have ordinary generating function
$$ \prod_{i=1}^k \frac{1}{1 - z^i}. $$
This applies to $\alpha$, since its parts correspond to column-wise extensions of height at most $k$, and $\alpha$ does not affect the number of parts $m$.
For $\beta$, each part contributes $1$ to the number of parts and contributes its size to the weight $n$. Thus each part of size $i \le k$ contributes a factor $w z^i$, and arbitrary multiplicities are allowed. The generating function is therefore
$$ \prod_{i=1}^k \frac{1}{1 - w z^i}. $$
The Durfee square itself contributes a fixed weight $z^{k^2}$.
Multiplying the three independent contributions gives the generating function for partitions with trace exactly $k$:
$$ \sum_{m,n} p(k,m,n) w^m z^n = z^{k^2} \prod_{i=1}^k \frac{1}{(1 - z^i)(1 - w z^i)}. $$
Hence,
$$ \boxed{\sum_{m,n} p(k,m,n), w^m z^n = z^{k^2} \prod_{i=1}^k \frac{1}{(1 - z^i)(1 - w z^i)} }. $$
Summation over $k$
Summing over all possible traces $k \ge 0$ produces the bivariate generating function for all partitions, refined by number of parts:
$$ \sum_{k \ge 0} \sum_{m,n} p(k,m,n) w^m z^n = \sum_{k \ge 0} z^{k^2} \prod_{i=1}^k \frac{1}{(1 - z^i)(1 - w z^i)}. $$
Since every partition has a unique trace, the left-hand side is also
$$ \sum_{m,n} p(m,n), w^m z^n, $$
where $p(m,n)$ denotes the number of partitions of $n$ with $m$ parts. Therefore,
$$ \boxed{\sum_{m,n} p(m,n), w^m z^n = \sum_{k \ge 0} z^{k^2} \prod_{i=1}^k \frac{1}{(1 - z^i)(1 - w z^i)} }. $$
This completes the derivation of the required identity. ∎