TAOCP 7.2.1.4 Exercise 8

Let $\alpha$ be a partition of $n$, written in frequency form as $\alpha:\quad 1^{c_1} 2^{c_2} 3^{c_3}\cdots,$ where $c_j \ge 0$ and $\sum_{j\ge 1} j c_j = n$.

taocpmathematicsalgorithmsvolume-4simple

Section 7.2.1.4: Generating All Partitions

Exercise 8. [15] [15] When (p1 . . . pt, q1 . . . qt) yields the rim representation of a partition a1a2 . . . as in (15) and (16), what’s the rim representation of the conjugate partition (a1a2 . . . )T ?

Verified: no
Solve time: 8m22s

Solution

Let $\alpha$ be a partition of $n$, written in frequency form as

$\alpha:\quad 1^{c_1} 2^{c_2} 3^{c_3}\cdots,$

where $c_j \ge 0$ and $\sum_{j\ge 1} j c_j = n$.

Define a map $\alpha \mapsto \beta$ as follows, treating each part size $j$ independently. For each $j \ge 1$:

if $c_j = 0$, no parts are produced;

if $c_j = 1$, include one part $j$ in $\beta$;

if $c_j \ge 2$, include one part $2j$ and also include $c_j - 2$ parts equal to $j$.

Let $d_k$ denote the multiplicities in $\beta$ obtained by this rule. The resulting multiset of parts defines $\beta$.

The total weight is preserved. For each fixed $j$ with $c_j \ge 2$, the contribution in $\beta$ is

$(c_j - 2)j + 2j = c_j j,$

and for $c_j \in {0,1}$ the contribution is unchanged. Summing over all $j$ yields the identity

$\sum j c_j = \sum \beta,$

so $\beta$ is a partition of $n$.

The construction is reversible. In $\beta$, every even part must arise as $2j$ from some $j$ with $c_j \ge 2$, and no other source produces even parts. Given $\beta$, for each even part $2j$ replace it by two copies of $j$, and keep every odd part $j$ unchanged. This reconstructs uniquely the multiplicities $c_j$, hence reconstructs $\alpha$. Therefore the map is a bijection between partitions of $n$.

Let $k$ be the number of distinct indices $j$ such that $c_j \ge 2$ in $\alpha$, meaning the number of part sizes repeated more than once. By construction, such a $j$ contributes exactly one even part $2j$ in $\beta$, and no other $j$ contributes an even part. Hence $\beta$ contains exactly $k$ even parts.

Conversely, every even part in $\beta$ arises from a unique $j$ with $c_j \ge 2$, so the number of part sizes repeated more than once in $\alpha$ equals the number of even parts in $\beta$.

The correspondence $\alpha \leftrightarrow \beta$ is therefore a one-to-one mapping satisfying the required equivalence. This completes the proof. ∎