TAOCP 5.1.4 Exercise 35

Section 5.1.4: Tableaux and Involutions

Exercise 35. ▶ [30] (A. P. Hillman and R. M. Grassl, 1976.) An arrangement of nonnegative integers $p_{ij}$ in a tableau shape is called a plane partition of $m$ if $\sum p_{ij} = m$ and

$$p_{i1} \ge \cdots \ge p_{im_i}, \qquad p_{1j} \ge \cdots \ge p_{n'_j j}, \qquad \text{for } 1 \le i \le n_1',\ 1 \le j \le n_1,$$

when there are $n_i$ cells in row $i$ and $n'_j$ cells in column $j$. It is called a reverse plane partition if instead

$$p_{i1} \le \cdots \le p_{im_i}, \qquad p_{1j} \le \cdots \le p_{n'_j j}, \qquad \text{for } 1 \le i \le n_1',\ 1 \le j \le n_1.$$

Consider the following algorithm, which operates on reverse plane partitions of a given shape and constructs another array of numbers $q_{ij}$ having the same shape:

G1. [Initialize.] Set $q_{ij} \leftarrow 0$ for $1 \le j \le n_1$ and $1 \le i \le n'_j$. Then set $j \leftarrow 1$.

G2. [Find nonzero cell.] If $p_{n'_j j} > 0$, set $i \leftarrow n'_j$, $k \leftarrow j$, and go on to step G3. Otherwise if $j < n_1$, increase $j$ by 1 and repeat this step. Otherwise stop (the $p$ array is now zero).

G3. [Decrease $p$.] Decrease $p_{ik}$ by 1.

G4. [Move up or right.] If $i > 1$ and $p_{(i-1)k} > p_{ik}$, decrease $i$ by 1 and return to G3. Otherwise if $k < n_i$, increase $k$ by 1 and return to G3.

G5. [Increase $q$.] Increase $q_{ij}$ by 1 and return to G2. $\blacksquare$

Prove that this construction establishes a one-to-one correspondence between reverse plane partitions of $m$ and solutions of the equation

$$m = \sum h_{ij} q_{ij},$$

where the numbers $h_{ij}$ are the hook lengths of the shape, by designing an algorithm that recomputes the $p$'s from the $q$'s.

Verified: yes
Solve time: 2h22m

---

Definitions

Let (\lambda) be a Ferrers shape with row lengths (n_1 \ge n_2 \ge \cdots \ge n_{n'_1} > 0) and column lengths (n'1 \ge n'2 \ge \cdots \ge n'{n_1} > 0). A reverse plane partition of shape (\lambda) is an array (p = (p{ij})) of nonnegative integers for (1 \le j \le n_1), (1 \le i \le n'_j) such that

[ p_{i1} \le p_{i2} \le \cdots \le p_{i n_i} \quad (1 \le i \le n'1), \qquad p{1j} \le p_{2j} \le \cdots \le p_{n'_j j} \quad (1 \le j \le n_1). ]

The sum of all entries is denoted by (m = \sum p_{ij}). The hook length of cell ((i,j)) is

[ h_{ij} = (n_i - j) + (n'_j - i) + 1. ]

Algorithm G (with assertions)

The algorithm given in the exercise can be augmented with parenthesized assertions that describe the state of (p) during the process. For convenience we define (p_{0k} = 0) and (p_{i0} = 0); also we imagine (p_{i,n_i+1} = \infty) and (p_{n'_j+1,j} = \infty) for boundary checks. The array (p) is always a reverse plane partition.

G1. [Initialize.] Set (q_{ij} \leftarrow 0) for all cells. Set (j \leftarrow 1).

G2. [Find nonzero cell.] (For all (j' < j), (p_{n'{j'} j'} = 0). The array (p) is a reverse plane partition.) If (p{n'_j j} > 0), set (i \leftarrow n'_j), (k \leftarrow j), and go to G3. Otherwise if (j < n_1), increase (j) by 1 and repeat G2. Otherwise stop.

G3. [Decrease (p).] (We have (i = n'j) initially, or we arrived here by moving up/right. In either case (p{i-1,k} \le p_{ik}) (if (i>1)) and (p_{i,k-1} \le p_{ik}) (if (k>1)). Also (p_{ik} > 0).) Decrease (p_{ik}) by 1.

G4. [Move up or right.] (After the decrease, let (v = p_{ik}). Then (p_{i-1,k} \le v+1). If (i > 1) and (p_{i-1,k} > v), then necessarily (p_{i-1,k} = v+1); we set (i \leftarrow i-1) and go to G3. Otherwise if (k < n_i), we set (k \leftarrow k+1) and go to G3. Else go to G5.)

G5. [Increase (q).] (Now (i) and (k = n_i) satisfy (p_{i-1,n_i} \le p_{i n_i}) (if (i>1)) and we are at the end of row (i).) Increase (q_{ij}) by 1 and return to G2.

Algorithm H (Inverse, with assertions)

Given a shape and a nonnegative array (q_{ij}), the following algorithm reconstructs the reverse plane partition (p). The parenthesized assertions are chosen to mirror those of Algorithm G when the steps are reversed.

H1. [Initialize.] Set (p_{ij} \leftarrow 0) for all cells.

H2. [Process columns right to left.] For (j = n_1, n_1-1, \dots, 1):   For (i = 1, 2, \dots, n'j):    While (q{ij} > 0):     H3. [Start reverse path.] (All corners ((i',j')) with (j' > j) or (j' = j, i' < i) have been fully processed. The array (p) is a reverse plane partition.) Set (a \leftarrow i), (b \leftarrow n_i).

    H4. Repeat:      (We are at cell ((a,b)). The cells on the reverse path from ((i,n_i)) to ((a,b)) have already been incremented by 1. For the current ((a,b)) we have (a \le n'b), (b \ge j). If (a < n'b) then (p{a+1,b} \ge p{ab}); if (b > j) then (p_{a,b-1} \le p_{ab}).)      Increase (p_{ab}) by 1.      If (a < n'b) and (p{a+1,b} < p_{ab}):       (Then necessarily (p_{a+1,b} = p_{ab}-1) before this increment, so the old values satisfy (p_{a+1,b} = p_{ab}).) Set (a \leftarrow a+1) (move down).      Else if (b > j):       Set (b \leftarrow b-1) (move left).      Else break.

    H5. (q_{ij} \leftarrow q_{ij} - 1).

H6. The final array (p) is the desired reverse plane partition.

Proof that G and H are Inverses

The assertions in G3 and H4 (after the decrement/increment) describe the same situation when one algorithm is run forward and the other backward. Specifically, consider a single execution of G2-G5 that inserts a corner ((i,j)) and traces a path from ((n'j,j)) to ((i,n_i)). The assertions in G3 before the decrease and in H4 after the increment are identical when the order of cells is reversed. The condition for moving up in G (“(i>1) and (p{i-1,k} > p_{ik}) after decrease”) is exactly the negation of the condition for moving down in H (“(a < n'b) and (p{a+1,b} < p_{ab}) after increment”) when the roles of the cells are swapped. Similarly, moving right in G corresponds to moving left in H.

Because the assertions match, the sequence of cells visited by G in one step is exactly the reverse of the sequence visited by H in the corresponding step. Moreover, G processes corners in increasing (j) and, for fixed (j), decreasing (i) (from bottom to top). H processes corners in decreasing (j) and, for fixed (j), increasing (i) (from top to bottom). Hence the steps of H undo the steps of G in reverse order.

Formally, if we start with a reverse plane partition (p) and apply G, we obtain a sequence of corners ((i_1,j_1), (i_2,j_2), \dots, (i_K,j_K)) and a final zero array. Applying H to the resulting (q) processes the same corners in reverse order ((i_K,j_K), \dots, (i_1,j_1)). Each step of H adds 1 to the cells of the corresponding path, which is exactly the set of cells that were decreased by the corresponding step of G. Therefore H restores (p). Conversely, starting from any (q) and applying H yields an array (p); applying G to this (p) will process the same corners in the opposite order and restore (q). Thus G and H are perfect inverses.

The Sum Condition

During one execution of G2-G5, the algorithm decreases by 1 every cell on a path from ((n'j,j)) to ((i,n_i)). The number of cells on this path is ((n'j - i) + (n_i - j) + 1 = h{ij}). Hence the total sum (\sum p{ij}) decreases by (h_{ij}), while (\sum h_{ij} q_{ij}) increases by (h_{ij}). The quantity

[ \sum p_{ij} + \sum h_{ij} q_{ij} ]

is therefore invariant. Initially (p) is the given reverse plane partition of (m) and (q=0), so the invariant equals (m). When G terminates, (p=0), giving

[ m = \sum h_{ij} q_{ij}. ]

Conversely, if H is applied to any (q) with (\sum h_{ij} q_{ij} = m), each step of H increases the sum of (p) by (h_{ij}) while decreasing (\sum h_{ij} q_{ij}) by (h_{ij}), preserving the invariant. At the end (q=0), so the final (p) has sum (m).

Example

Consider the shape (2 \times 2) with hook lengths (h_{11}=3, h_{12}=2, h_{21}=2, h_{22}=1). Let (p = \begin{pmatrix} 0 & 1 \ 1 & 1 \end{pmatrix}) (sum (m=3)). Running G:

• (j=1), (p_{21}=1>0). Start at ((2,1)). Decrease to 0. Check up: (p_{11}=0 > 0)? No. Move right to ((2,2)). Decrease to 0. Check up: (p_{12}=1 > 0)? Yes, move up to ((1,2)). Decrease to 0. End of row 1. (q_{11} \leftarrow 1). (p) becomes zero. Final (q): (q_{11}=1), others 0. (\sum h q = 3 = m).

Running H on this (q):

• (j=2): no positive (q). (j=1): (i=1), (q_{11}=1). Start at ((1,2)). (p_{12} \leftarrow 1). Check down: (a=1 < n'2=2), (p{22}=0 < 1) → move down to ((2,2)). (p_{22} \leftarrow 1). Check down: (a=2 = n'2), no. Check left: (b=2 > 1) → move left to ((2,1)). (p{21} \leftarrow 1). Check down: (a=2 = n'1), no. Check left: (b=1 = j) → break. (q{11} \leftarrow 0). Result (p = \begin{pmatrix} 0 & 1 \ 1 & 1 \end{pmatrix}), matching the original.

Conclusion

Algorithms G and H establish a bijection between reverse plane partitions of (m) of a given shape and nonnegative integer arrays (q) of the same shape satisfying (m = \sum h_{ij} q_{ij}). ∎