TAOCP 7.2.1.4 Exercise 7

Let $a_1 \ge \cdots \ge a_n \ge 0$ and $a'_1 \ge \cdots \ge a'_n \ge 0$ be partitions of $n$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.1.4: Generating All Partitions

Exercise 7. [M20] [M20] Suppose a1 . . . an and a′ 1 . . . a′ n are partitions of n with a1 ≥· · · ≥an ≥0 and a′ 1 ≥· · · ≥a′ n ≥0, and let their respective conjugates be b1 . . . bn = (a1 . . . an)T, b′ 1 . . . b′ n = (a′ 1 . . . a′ n)T. Show that b1 . . . bn < b′ 1 . . . b′ n if and only if an . . . a1 < a′ n . . . a′ 1.

Verified: no
Solve time: 20m58s

Solution

Let $a_1 \ge \cdots \ge a_n \ge 0$ and $a'_1 \ge \cdots \ge a'_n \ge 0$ be partitions of $n$. Let

$$ b_k = #{j : a_j \ge k}, \qquad b'_k = #{j : a'_j \ge k}. $$

Then $(b_1,\dots,b_n)$ and $(b'_1,\dots,b'_n)$ are conjugate partitions.

Let $c_k$ and $c'_k$ denote the multiplicities of parts equal to $k$ in $a$ and $a'$. Then

$$ b_k - b_{k+1} = c_k, \qquad b'k - b'{k+1} = c'_k $$

for $1 \le k < n$, with $b_{n+1}=b'_{n+1}=0$. Hence each sequence $(b_k)$ determines and is determined by the multiplicity sequence $(c_k)$.

Let $k$ be the smallest index such that $b_k \ne b'_k$. Then $b_j=b'_j$ for all $j<k$. Subtracting consecutive equalities gives $c_j=c'_j$ for all $j<k-1$. Moreover,

$$ c_{k-1} = b_{k-1} - b_k, \qquad c'{k-1} = b'{k-1} - b'_k, $$

so $c_{k-1} \ne c'{k-1}$ because $b{k-1}=b'_{k-1}$ and $b_k \ne b'_k$. Thus the first index at which $(c_k)$ and $(c'_k)$ differ is $k-1$.

The reversed sequence $a_n,\dots,a_1$ consists of $c_1$ copies of $1$, followed by $c_2$ copies of $2$, and so on. The same structure holds for $a'_n,\dots,a'_1$. Since $c_j=c'_j$ for $j<k-1$, both reversed sequences agree through all entries corresponding to parts $1,2,\dots,k-2$. The first possible discrepancy occurs inside the block of entries equal to $k-1$.

Within that block, one sequence contains exactly $c_{k-1}$ copies of $k-1$ and the other contains $c'{k-1}$ copies. Because all earlier blocks coincide, lexicographic comparison of $a_n \cdots a_1$ and $a'n \cdots a'1$ is decided by the first position in this $(k-1)$-block where the two sequences differ, which is determined by whether $c{k-1} < c'{k-1}$ or $c{k-1} > c'_{k-1}$.

Since

$$ b_k - b'k = (b{k-1}-c_{k-1}) - (b'{k-1}-c'{k-1}) = c'{k-1} - c{k-1}, $$

the sign of the first difference in $(b_k)$ matches the lexicographic comparison of the reversed sequences.

Therefore $b_1 \cdots b_n < b'_1 \cdots b'_n$ holds if and only if $a_n \cdots a_1 < a'_n \cdots a'_1$.

This completes the proof. ∎