TAOCP 7.2.1.4 Exercise 3

Section 7.2.1.4: Generating All Partitions

Exercise 3. [M17] [M17] A partition a1 + · · · + am of n into m parts a1 ≥· · · ≥am is optimally balanced if |ai −aj| ≤1 for 1 ≤i, j ≤m. Prove that there is exactly one such partition, whenever n ≥m ≥1, and give a simple formula that expresses the jth part aj as a function of j, m, and n.

Verified: no
Solve time: 3m57s

Solution

The rim representation $(p_1 \ldots p_t, q_1 \ldots q_t)$ encodes the boundary (outer rim) of the Ferrers diagram of the partition $a_1 a_2 \ldots$ as an alternating sequence of maximal horizontal and vertical segments. In the standard construction in (15) and (16), the rim is traced from the northeast corner of the diagram toward the southwest corner, decomposed into horizontal runs of lengths $p_1, p_2, \ldots, p_t$ interleaved with vertical runs of lengths $q_1, q_2, \ldots, q_t$.

The conjugate partition $(a_1 a_2 \ldots)^T$ corresponds to reflecting the Ferrers diagram across the main diagonal. This reflection interchanges rows and columns, hence it swaps horizontal and vertical directions of every boundary segment. A horizontal run of length $p_i$ in the original rim becomes a vertical run of the same length in the conjugate rim, and a vertical run of length $q_i$ becomes a horizontal run of the same length.

The boundary traversal order is also reversed under this reflection, since the northeast-to-southwest motion of the original rim becomes a northwest-to-southeast motion in the conjugate diagram. Consequently, the sequence of segments must be read in reverse order.

Thus, the rim representation of the conjugate partition is obtained by reversing the sequence and swapping each pair $(p_i, q_i)$. The conjugate rim representation is

$$ (q_t, p_t), (q_{t-1}, p_{t-1}), \ldots, (q_1, p_1). $$

Equivalently, if $(p_1 \ldots p_t, q_1 \ldots q_t)$ represents $a_1 a_2 \ldots$, then the rim representation of $(a_1 a_2 \ldots)^T$ is

$$ (q_1' \ldots q_t', p_1' \ldots p_t') \quad \text{with} \quad (p_i', q_i') = (q_{t+1-i}, p_{t+1-i}). $$

This completes the determination of the rim representation of the conjugate partition. ∎