Section 7.2.1.4: Generating All Partitions

Exercise 17. [M26] [M26] A joint partition of n is a pair of sequences (a1, . . . , ar; b1, . . . , bs) of positive integers for which we have a1 ≥· · · ≥ar, b1 > · · · > bs, and a1 + · · · + ar + b1 + · · · + bs = n. Thus it is an ordinary partition if s = 0, and a partition into distinct parts if r = 0. a) Find a simple formula for the generating function ur+svszn, summed over all joint partitions of n with r ordinary parts ai and s distinct parts bj. b) Similarly, find a simple formula for vszn when the sum is over all joint partitions that have exactly r+s = t total parts, given the value of t. For example, the answer when t = 2 is (1 + v)(1 + vz)z2/((1 −z)(1 −z2)). c) What identity do you deduce?

Verified: no
Solve time: 8m12s

---

Solution

Let a partition of $n$ have Ferrers diagram with Durfee square of size $k$, meaning that the largest square subdiagram is $k\times k$. This condition is equivalent to requiring that $\lambda_k \ge k$ and $\lambda_{k+1} < k$.

Fix $k\ge 0$. Every such partition decomposes uniquely into three parts.

The $k\times k$ Durfee square contributes weight $z^{k^2}$ and forces $k$ parts, one in each of the first $k$ rows.

The cells to the right of the Durfee square in the first $k$ rows form a partition $\mu$ with at most $k$ parts, where the $i$th row contributes $\mu_i \ge 0$ additional cells. The size contribution is $|\mu| = \mu_1 + \cdots + \mu_k$, giving generating function

$$ \prod_{i=1}^k \frac{1}{1 - z^i}. $$

This is the standard generating function for partitions with at most $k$ parts after conjugation.

The cells below the Durfee square form a partition $\nu$ with at most $k$ parts, where $\nu_j$ counts the number of cells in column $j$ below row $k$. Each part of $\nu$ contributes both to size and to the number of parts of the full partition, since each nonzero row below the Durfee square increases the total number of parts by $1$. Marking the number of parts by $w$, this contribution has generating function

$$ \prod_{i=1}^k \frac{1}{1 - w z^i}. $$

The Durfee square itself contributes $k$ parts, giving the factor $w^k$. Combining all contributions yields

$$ \sum_{m,n} p(k,m,n) w^m z^n

\frac{w^k z^{k^2}}{\left(\prod_{i=1}^k (1 - z^i)\right)\left(\prod_{i=1}^k (1 - w z^i)\right)}. $$

Thus,

$$ \sum_{m,n} p(k,m,n) w^m z^n

\frac{w^k z^{k^2}}{\prod_{i=1}^k (1 - z^i)(1 - w z^i)}. $$

Summing over all possible trace values $k$ gives all partitions with parts counted by $w$ and size counted by $z$. Hence

$$ \sum_{k\ge 0}\sum_{m,n} p(k,m,n) w^m z^n

\sum_{k\ge 0} \frac{w^k z^{k^2}}{\prod_{i=1}^k (1 - z^i)(1 - w z^i)}. $$

The left-hand side reduces to the ordinary bivariate generating function for partitions where $w$ marks the number of parts, since every partition has a unique Durfee size:

$$ \sum_{m,n} p(m,n) w^m z^n

\prod_{i\ge 1}\frac{1}{1 - w z^i}. $$

Therefore,

$$ \sum_{k\ge 0} \frac{w^k z^{k^2}}{\prod_{i=1}^k (1 - z^i)(1 - w z^i)}

\prod_{i\ge 1}\frac{1}{1 - w z^i}. $$

Setting $w=1$ yields the identity

$$ \sum_{k\ge 0} \frac{z^{k^2}}{\left(\prod_{i=1}^k (1 - z^i)\right)^2}

\prod_{i\ge 1}\frac{1}{1 - z^i}, $$

which equates a Durfee-square decomposition sum with the ordinary partition generating function.

This completes the proof. ∎