TAOCP 7.2.1.4 Exercise 14

Section 7.2.1.4: Generating All Partitions

Exercise 14. ▶ [M28] [M28] (J. J. Sylvester, 1882.) Find a one-to-one correspondence between parti- tions of n into distinct parts a1 > a2 > · · · > am that have exactly k “gaps” where aj > aj+1 + 1, and partitions of n into odd parts that have exactly k + 1 different values. (For example, when k = 0 this construction proves that the number of ways to write n as a sum of consecutive integers is the number of odd divisors of n.)

Verified: no
Solve time: 19m21s

Solution

Let $\alpha$ be a self-conjugate partition of $n$. Its Ferrers diagram is symmetric with respect to the main diagonal. For each cell $(i,i)$ on the diagonal, consider the hook consisting of that cell together with all cells to its right in row $i$ and all cells below it in column $i$. Because the diagram is symmetric, each such hook is determined entirely by its intersection with the diagonal structure, and these diagonal hooks are disjoint and cover all cells of the diagram.

If the diagonal has $d$ cells, then the $i$th diagonal hook has length

$$ h_i = 2a_i - 2i + 1, $$

where $a_i$ is the length of row $i$ of $\alpha$. Each $h_i$ is a positive odd integer, and the symmetry of the Ferrers diagram implies that

$$ h_1 > h_2 > \cdots > h_d, $$

since successive diagonal positions strictly decrease both row length and column length. Thus every self-conjugate partition determines a partition of $n$ into distinct odd parts.

Conversely, given a partition of $n$ into distinct odd parts

$$ n = (2b_1 - 1) + (2b_2 - 1) + \cdots + (2b_d - 1), \quad b_1 > b_2 > \cdots > b_d \ge 1, $$

one reconstructs a self-conjugate Ferrers diagram by placing diagonal hooks of lengths $2b_i - 1$ at diagonal positions and filling symmetrically. The reconstruction is unique because each hook determines exactly one diagonal cell and the symmetry condition forces all off-diagonal cells.

This establishes a bijection between self-conjugate partitions and partitions into distinct odd parts. Therefore the ordinary generating function for self-conjugate partitions is the generating function for partitions into distinct odd parts.

A partition into distinct odd parts uses each odd integer $2k-1$ at most once. The contribution of the part $2k-1$ is either absent or present once, giving a factor

$$ 1 + x^{2k-1}. $$

Independence over all odd parts yields the product

$$ \prod_{k \ge 1} (1 + x^{2k-1}). $$

Thus the generating function for self-conjugate partitions is

$$ \sum_{n \ge 0} s(n)x^n = \prod_{k \ge 1} (1 + x^{2k-1}), $$

where $s(n)$ denotes the number of self-conjugate partitions of $n$.

$$ \boxed{\prod_{k \ge 1} (1 + x^{2k-1})} $$