TAOCP 7.2.1.4 Exercise 13
A partition $\alpha$ is self-conjugate when its Ferrers diagram is symmetric across the main diagonal.
Section 7.2.1.4: Generating All Partitions
Exercise 13. ▶ [M23] [M23] (F. Franklin, 1882.) Find a one-to-one correspondence α ↔β between partitions of n such that α has exactly k parts repeated more than once if and only if β has exactly k even parts. (For example, the partition 64421111 has two repeated parts {4, 1} and three even parts {6, 4, 2}. The case k = 0 corresponds to Euler’s result.)
Verified: no
Solve time: 6m55s
Solution
A partition $\alpha$ is self-conjugate when its Ferrers diagram is symmetric across the main diagonal. The diagonal cells form a staircase of size $k$ for some $k \ge 0$, and the diagram is determined by the hook lengths emanating symmetrically from these $k$ diagonal cells.
Let the $i$-th diagonal cell have arm length $a_i$ to the right and leg length $a_i$ downward. Self-conjugacy forces equality of arm and leg lengths, so each diagonal cell contributes a hook of size $2a_i + 1$, and these hook sizes are strictly decreasing as $i$ increases. Equivalently, the partition is determined by a strictly decreasing sequence of positive integers of the form $2a_i+1$, hence by a partition into distinct odd parts.
Conversely, given a partition into distinct odd parts
$\lambda_1 > \lambda_2 > \cdots > \lambda_k,$
with each $\lambda_i = 2a_i+1$, one constructs a Ferrers diagram with $k$ diagonal cells, and the $i$-th diagonal cell having arm and leg length $a_i$. The strict decrease of the $\lambda_i$ ensures the diagram fits and produces a valid partition, and symmetry across the diagonal holds by construction. This correspondence is bijective between self-conjugate partitions and partitions into distinct odd parts.
The generating function for partitions into distinct odd parts is obtained by independent choice of each odd part $2j-1$, either included once or not included. Each inclusion contributes weight $x^{2j-1}$, and exclusion contributes $1$, so each part contributes a factor $(1 + x^{2j-1})$. Multiplying over all odd integers gives the full generating function
$\sum_{n \ge 0} sc(n)x^n = \prod_{j \ge 1} (1 + x^{2j-1}).$
This completes the derivation of the generating function. ∎