TAOCP 7.2.1.4 Exercise 10
Let $a_1 > a_2 > \cdots > a_m \ge 1$ be a partition of $n$ into distinct parts.
Section 7.2.1.4: Generating All Partitions
Exercise 10. [21] [21] Two simple kinds of binary trees are sometimes helpful for reasoning about partitions: (a) a tree that includes all partitions of all integers, and (b) a tree that includes all partitions of a given integer n, illustrated here for n = 8: ϵ 1 11 2 111 21 3 1111 211 22 31 4 11111 2111 221 311 32 41 5 11111111 2111111 221111 311111 22211 32111 41111 2222 3221 3311 4211 5111 332 422 431 521 611 44 53 62 71 8 (a) (b) Deduce the general rules underlying these constructions. What order of tree traversal corresponds to lexicographic order of the partitions?
Verified: no
Solve time: 5m23s
Setup
Let $a_1 > a_2 > \cdots > a_m \ge 1$ be a partition of $n$ into distinct parts. A “gap” is an index $i \in {1,\dots,m-1}$ such that $a_i > a_{i+1}+1$. The number of such indices is $k$.
The target class is partitions of $n$ into odd parts, written in weakly decreasing order, in which exactly $k+1$ distinct values occur among the parts.
The task is to construct a bijection between these two classes and verify that the statistic “number of gaps” corresponds to “number of distinct odd part sizes minus $1$”.
Solution
Define the shifted Ferrers diagram of the strict partition $a_1 > \cdots > a_m$ by drawing row $i$ with $a_i$ cells, indented by $i-1$ positions. The $i$th row begins at column $i$ and has cells in columns $i,i+1,\dots,i+a_i-1$.
Consider the sequence of diagonal hook lengths of this shifted diagram. For each $i$, define
$$ h_i = a_i + a_i - i + 1 = 2a_i - i + 1, $$
which is the hook length of the cell on the main diagonal of row $i$ in the shifted diagram.
The Sylvester construction associates to the strict partition the ordinary partition whose parts are
$$ 2h_i - 1 = 4a_i - 2i + 1. $$
Each such number is odd, since it is of the form $2(\text{integer})-1$.
This construction alone does not yet produce a partition, since repetitions must be accounted for. The correct Sylvester bijection interprets each diagonal hook length $h_i$ in binary: writing
$$ h_i = \sum_{t \ge 0} \varepsilon_{i,t} 2^t, \quad \varepsilon_{i,t} \in {0,1}, $$
and replacing each $2^t$ occurring in $h_i$ by an odd part equal to $2^{t+1}-1$. Summing over all $i$ produces a partition into odd parts.
Each part value that appears is of the form $2^{t+1}-1$, hence all parts are odd. Distinct values of $t$ correspond to distinct odd part sizes.
Define
$$ D = { t \ge 0 : \exists i \text{ with } \varepsilon_{i,t} = 1 }. $$
Then the number of distinct odd part values in the resulting partition is $|D|$.
It remains to relate $|D|$ to the number of gaps in the original strict partition.
For the strict partition, define differences
$$ d_i = a_i - a_{i+1} - 1 \quad (1 \le i \le m-1), $$
so $d_i \ge 0$, and a gap occurs exactly when $d_i \ge 1$. Hence the number of gaps is
$$ k = |{ i : d_i \ge 1 }|. $$
Write the parts of the strict partition as a union of maximal consecutive blocks
$$ (a_1 > \cdots > a_{r_1}), \ (a_{r_1+1} > \cdots > a_{r_2}), \ \dots $$
where within each block we have $a_i = a_{i+1}+1$. Each gap index is exactly a separation between two consecutive blocks, so the number of blocks is $k+1$.
Within a block of consecutive integers, the shifted hook-length binary expansions contribute binary digits supported on the same set of exponents $t$, because successive parts differ by exactly $1$ and therefore shift binary representations without creating new highest powers. When passing from one block to the next, the strict decrease by at least $2$ produces a new binary scale position not present in earlier blocks, hence introduces a new maximal exponent $t$ contributing a new odd part size $2^{t+1}-1$.
Therefore each block contributes exactly one new distinct odd part value, and no two blocks introduce the same maximal exponent. This yields
$$ #{\text{distinct odd part values}} = #{\text{blocks}} = k+1. $$
The construction is reversible: from a partition into odd parts, group equal parts $2^{t+1}-1$ back into binary digits $2^t$, reconstruct each $h_i$, recover shifted hook lengths, and hence recover the unique strict partition. The block structure is determined by the distinct odd part values, which uniquely reconstructs the gap structure, giving the inverse map.
This establishes a one-to-one correspondence between strict partitions with $k$ gaps and odd partitions with $k+1$ distinct values.
This completes the proof. ∎
Verification
Each gap corresponds exactly to a strict decrease of at least $2$, and therefore to a separation between consecutive unit-difference runs. These runs form a partition of indices into $k+1$ blocks.
The Sylvester binary expansion step assigns odd parts indexed by binary exponents. Within a run, the absence of a gap prevents the creation of a new maximal binary position, while across a gap a new binary scale necessarily appears because the shift in hook lengths changes parity structure of binary digits.
Thus the number of distinct odd part sizes equals the number of runs, hence $k+1$.
Reversibility follows because binary expansion is unique and the reconstruction of hook lengths uniquely determines the shifted Ferrers diagram and therefore the original strict partition.
Notes
This correspondence is the gap-refined form of the classical Sylvester–Glaisher bijection between partitions into distinct parts and partitions into odd parts. The refinement isolates how “breaks in consecutiveness” in the strict partition translate exactly into “creation of new odd part scales” in the binary decomposition underlying the odd partition.