TAOCP 7.2.1.4 Exercise 18
Let $t=r+s$.
Section 7.2.1.4: Generating All Partitions
Exercise 18. ▶ [M23] [M23] (Doron Zeilberger.) Show that there is a one-to-one correspondence be- tween pairs of integer sequences (a1, a2, . . . , ar; b1, b2, . . . , bs) such that a1 ≥a2 ≥· · · ≥ar, b1 > b2 > · · · > bs, and pairs of integer sequences (c1, c2, . . . , cr+s; d1, d2, . . . , dr+s) such that c1 ≥c2 ≥· · · ≥cr+s, dj ∈{0, 1} for 1 ≤j ≤r + s, related by the multiset equations {a1, a2, . . . , ar} = {cj | dj = 0} and {b1, b2, . . . , bs} = {cj + r + s −j | dj = 1}. Consequently we obtain the interesting identity a1≥···≥ar>0, r≥0 b1>···>bs>0, s≥0 ur+svsza1+···+ar+b1+···+bs = c1≥···≥ct>0, t≥0 d1,...,dt∈{0,1} utvd1+···+dtzc1+···+ct+(t−1)d1+···+dt−1.
Verified: no
Solve time: 29m25s
Solution
Let $t=r+s$. We construct a map from a pair
$$ (a_1 \ge \cdots \ge a_r > 0;; b_1 > \cdots > b_s > 0) $$
to a pair
$$ (c_1 \ge \cdots \ge c_t > 0;; d_1,\ldots,d_t \in {0,1}) $$
satisfying the multiset conditions in the statement.
The construction proceeds by viewing both sequences as Ferrers diagrams, where the $a$-parts form an ordinary partition diagram and the $b$-parts form a strict partition diagram drawn in shifted form. The strictness of $b_1>\cdots>b_s$ means that its Ferrers diagram can be placed so that the $i$-th row is indented by $i-1$ cells. This shifted diagram can then be aligned against a staircase of width $t$, producing a configuration in which every column $j$ has a well-defined height $c_j$, and each column is marked according to whether it contains a cell originating from the shifted $b$-diagram. Define $d_j=1$ if column $j$ contains at least one shifted $b$-cell, and $d_j=0$ otherwise.
The column heights form a weakly decreasing sequence $c_1 \ge \cdots \ge c_t$, since Ferrers diagrams have nonincreasing row lengths and column heights inherit this monotonicity. Every column contains at least one cell from either the $a$-diagram or the shifted $b$-diagram, hence each $c_j>0$.
By construction, the cells originating from the $a$-diagram contribute exactly the multiset ${a_1,\ldots,a_r}$, since these rows are unshifted and are distributed across columns without altering their intrinsic row lengths. This yields
$$ {a_1,\ldots,a_r} = {c_j \mid d_j=0}. $$
For columns containing shifted $b$-cells, let $b_i$ be the part whose shifted row contributes to column $j$. In the shifted Ferrers diagram, the $i$-th row is displaced by $i-1$ columns, so a cell lying in column $j$ corresponds to original height contribution reduced by $t-j$ relative to the staircase alignment. Hence the relationship between the original part $b_i$ and the column height is
$$ b_i = c_j + (t-j), $$
which gives
$$ {b_1,\ldots,b_s} = {c_j + t - j \mid d_j=1}. $$
This establishes that the construction satisfies the required multiset equations.
To prove that $b_1>\cdots>b_s$ follows from the construction, take two indices $j<k$ with $d_j=d_k=1$. Then
$$ b_j = c_j + t - j,\qquad b_k = c_k + t - k. $$
Since $c_j \ge c_k$ and $t-j > t-k$, it follows that
$$ b_j \ge c_k + (t-j) > c_k + (t-k) = b_k, $$
so the sequence $b$ is strictly decreasing.
To prove that $a_1\ge \cdots \ge a_r$, observe that the $a$-parts are exactly those column heights $c_j$ with $d_j=0$. Any subsequence of a weakly decreasing sequence is weakly decreasing, so the $a$-sequence inherits the required order.
This defines a map from $(a,b)$ to $(c,d)$.
For invertibility, start from a pair $(c_1\ge \cdots \ge c_t; d_1,\ldots,d_t)$. Define
$$ a_i \in {c_j \mid d_j=0}, \qquad b_i = c_j + t - j \text{ for each } j \text{ with } d_j=1. $$
The argument above shows that the resulting $b$-sequence is strictly decreasing and positive, while the $a$-sequence is weakly decreasing and positive. This reconstruction recovers the original pair uniquely, since the positions of $d_j$ determine exactly which entries are shifted.
Thus the mapping is bijective.
The identity follows by summing $u^{r+s} v^{d_1+\cdots+d_t} z^{\sum c_j + \sum_{d_j=1}(t-j)}$ over all $(c,d)$, which matches term-by-term with the corresponding weight $u^r v^s z^{\sum a_i + \sum b_i}$ under the bijection.
This completes the proof. ∎