TAOCP 7.2.1.4 Exercise 4
Let the Ferrers diagram of $a_1a_2\cdots a_m$ consist of cells $(i,j)$ with $1\le i\le m$ and $1\le j\le a_i$.
Section 7.2.1.4: Generating All Partitions
Exercise 4. [M22] [M22] (Gideon Ehrlich, 1974.) What is the lexicographically smallest partition of n in which all parts are ≥r? For example, when n = 19 and r = 5 the answer is 766.
Verified: no
Solve time: 8m24s
Solution
Let the Ferrers diagram of $a_1a_2\cdots a_m$ consist of cells $(i,j)$ with $1\le i\le m$ and $1\le j\le a_i$. The conjugate partition $b_1b_2\cdots b_m$ is defined by
$$ b_j = |{, i : a_i \ge j ,}|. $$
Define the set
$$ S = {a_i + i : 1\le i\le m}, \quad T = {b_j + j : 1\le j\le m}. $$
The boundary of the Ferrers diagram is the lattice path from $(0,m)$ to $(a_1,0)$ consisting of unit steps east and south, enclosing exactly the cells of the diagram. Each row $i$ ends at the point $(a_i,i)$ on this boundary. Each column $j$ ends at the point $(j,b_j)$ on the boundary.
For each $i$, the row endpoint $(a_i,i)$ lies on the diagonal $x+y = a_i + i$, so each element of $S$ is the diagonal index of a unique east endpoint of the boundary.
For each $j$, the column endpoint $(j,b_j)$ lies on the same family of diagonals, and contributes the diagonal index $b_j + j$, so each element of $T$ is the diagonal index of a unique south endpoint of the boundary.
The boundary path has exactly one vertex on each maximal horizontal segment and exactly one vertex on each maximal vertical segment, and each such vertex is either a row endpoint or a column endpoint. Every turn of the boundary is shared by exactly one row endpoint and exactly one column endpoint after projection onto diagonals $x+y=\text{constant}$, so the multiset of diagonal indices determined by row endpoints coincides with the multiset determined by column endpoints.
Formally, consider any integer $k$. The condition $k\in S$ holds exactly when there exists an $i$ such that the boundary has an east endpoint at $(a_i,i)$ on the diagonal $x+y=k$, equivalently a transition from a vertical step to a horizontal step occurs at level $k-i$. The condition $k\in T$ holds exactly when there exists a $j$ such that the boundary has a south endpoint at $(j,b_j)$ on the same diagonal, equivalently a transition from a horizontal step to a vertical step occurs at level $k-j$. These transitions correspond bijectively along the same boundary path, since each corner of the Ferrers boundary is simultaneously the end of a row and the end of a column in the conjugate diagram.
Thus every diagonal index $k$ arising as some $a_i+i$ arises equally often as some $b_j+j$, and vice versa, so the multisets coincide.
$$ \boxed{{a_1+1,a_2+2,\ldots,a_m+m}={b_1+1,b_2+2,\ldots,b_m+m}} $$
This completes the proof. ∎