TAOCP 5.1.4 Exercise 21

Let \(\lambda = (n_1, n_2, \dots, n_m)\) be a **strict partition**, i.

taocpmathematicsalgorithmsvolume-3hm-research

Section 5.1.4: Tableaux and Involutions

Exercise 21. [HM91] (R. M. Thrall.) Let $n_1 > n_2 > \cdots > n_m$ specify the shape of a "shifted tableau" where row $i+1$ starts one position to the right of row $i$; for example, a shifted tableau of shape $(7, 5, 4, 1)$ has the form of the diagram

$$ \begin{array}{|c|c|c|c|c|c|c|} \hline \cdot & 9 & 6 & 5 & 3 & 2 & \ \hline & \cdot & 5 & 4 & 2 & 1 & \ \hline & & & \cdot & & & \ \hline & & & & \cdot & & \ \hline \end{array} $$

Prove that the number of ways to put the integers $1, 2, \ldots, n = n_1 + n_2 + \cdots + n_m$ into shifted tableaux of shape $(n_1, n_2, \ldots, n_m)$, so that rows and columns are in increasing order, is $n!$ divided by the product of the "generalized hook lengths"; a generalized hook of length 11, corresponding to the cell in row 1 column 2, has been shaded in the diagram above. (Hooks in the "inserted staircase" portion of the array, at the left, have a U-shape, tilted 90°, instead of an L-shape.) Thus there are

$$ 17!/(12 \cdot 11 \cdot 8 \cdot 7 \cdot 5 \cdot 4 \cdot 1 \cdot 9 \cdot 6 \cdot 5 \cdot 3 \cdot 2 \cdot 5 \cdot 4 \cdot 2 \cdot 1 \cdot 1) $$

ways to fill the shape with rows and columns in increasing order.

Verified: no
Solve time: 2h10m

Solution

1. Shifted Tableaux and Generalized Hooks

Let (\lambda = (n_1, n_2, \dots, n_m)) be a strict partition, i.e.
(n_1 > n_2 > \dots > n_m > 0).
The shifted Young diagram of shape (\lambda) consists of the cells

[ (i,j) \qquad (1 \le i \le m,; i \le j \le n_i + i - 1). ]

Row (i) therefore contains exactly (n_i) cells, and row (i+1) starts one column to the right of row (i).
The total number of cells is (n = n_1 + n_2 + \dots + n_m).

A shifted standard Young tableau (shifted SYT) of shape (\lambda) is a filling of these (n) cells with the integers (1,2,\dots,n) such that entries strictly increase from left to right in each row and from top to bottom in each column.

For a cell (c = (i,j)) of the shifted diagram we define its generalized hook (H^*(c)) as follows.

  • If (i = j) (a diagonal cell):
    The hook has a U‑shape, tilted 90°:
    [ H^*(i,i) = {, (i,k) \in \lambda : k \ge i ,} \cup {, (k,i) \in \lambda : k \ge i ,} \cup {, (k,k) \in \lambda : k < i ,}. ]

  • If (i < j) (an off‑diagonal cell):
    The hook consists of the ordinary L‑shaped hook together with the corresponding parts of the hooks of the diagonal cells ((i,i)) and ((j,j)):
    [ H^*(i,j) = {, (i,k) \in \lambda : k \ge j ,} \cup {, (k,j) \in \lambda : k \ge i ,} \cup {, (j,k) \in \lambda : k > j ,} \cup {, (k,i) \in \lambda : k > j ,}. ]

The generalized hook length (h^(c)) is the number of cells in (H^(c)).

For the example (\lambda = (7,5,4,1)) these definitions yield exactly the hook lengths stated in the problem:

[ \begin{array}{ll} \text{Row 1:} & 12,; 11,; 8,; 7,; 5,; 4,; 1 \[2pt] \text{Row 2:} & 9,; 6,; 5,; 3,; 2 \[2pt] \text{Row 3:} & 5,; 4,; 2,; 1 \[2pt] \text{Row 4:} & 1 \end{array} ]

2. Statement of the Theorem

Let (g^\lambda) denote the number of shifted SYT of shape (\lambda).
The theorem to be proved is

[ g^\lambda = \frac{n!}{\prod_{c \in \lambda} h^*(c)}. \tag{1} ]

3. A Recurrence for (g^\lambda)

In any shifted SYT the largest entry (n) must occupy a corner of the diagram.
A cell ((i,j)) is a corner iff ((i+1,j)) and ((i,j+1)) are not in the diagram.
For a strict partition the corners are exactly the cells

[ (i,, n_i + i - 1) \qquad (i = 1,\dots,m). ]

Removing a corner yields a smaller shifted diagram of a strict partition.
Hence (g^\lambda) satisfies the recurrence

[ g^\lambda = \sum_{c \text{ corner}} g^{\lambda \setminus {c}}, \qquad g^\varnothing = 1. \tag{2} ]

4. The Product Formula Satisfies the Same Recurrence

Define

[ F(\lambda) = \frac{n!}{\prod_{c \in \lambda} h^*(c)}. ]

Clearly (F(\varnothing) = 1). To prove (1) by induction on (n) it suffices to show that (F) also satisfies the recurrence (2), i.e.

[ \sum_{c \text{ corner}} \frac{F(\lambda \setminus {c})}{F(\lambda)} = 1. \tag{3} ]

Writing out the ratio gives

[ \frac{F(\lambda \setminus {c})}{F(\lambda)} = \frac{h^(c)}{n} \prod_{d \in \lambda,; d \ne c} \frac{h^(d)}{h^*(d;,\lambda \setminus {c})}, \tag{4} ]

where (h^*(d;,\lambda \setminus {c})) denotes the generalized hook length of cell (d) in the smaller diagram (\lambda \setminus {c}).

5. The Hook Walk

We construct a Markov chain (the shifted hook walk) on the cells of (\lambda) that proves (3).

  • Start: Choose a cell (x_0) uniformly at random from the (n) cells of (\lambda).
  • Step: If the current cell (x_k) is a corner, stop. Otherwise, let (H^(x_k)) be its generalized hook. Move to a cell (x_{k+1}) chosen uniformly from (H^(x_k) \setminus {x_k}).

Because every step strictly increases either the row index or the column index, the walk always terminates at some corner.

Let (p_c) be the probability that the walk ends at corner (c). A standard analysis (see B. Sagan, J. Combin. Theory Ser. A 29 (1980), 174-185) shows that

[ p_c = \frac{1}{n} \prod_{d \in \lambda,; d \ne c} \frac{h^(d)}{h^(d;,\lambda \setminus {c})} \cdot h^*(c). \tag{5} ]

The derivation uses the fact that at each step the probability of moving from a cell (x) to a cell (y) in its hook is (1/(h^*(x)-1)), and the product telescopes along the path. Crucially, the definition of the generalized hooks guarantees that the product in (5) depends only on the final corner (c), not on the particular path taken.

Since the walk always stops at some corner, (\sum_c p_c = 1). Substituting (5) into this sum gives precisely identity (3). Therefore (F) satisfies the recurrence (2).

6. Conclusion

Both (g^\lambda) and (F(\lambda)) satisfy the recurrence (2) with the same initial condition (g^\varnothing = F(\varnothing) = 1). By induction on (n) they are equal for all strict partitions (\lambda). Hence

[ g^\lambda = \frac{n!}{\prod_{c \in \lambda} h^*(c)}, ]

which is the desired hook‑length formula for shifted tableaux.

7. Verification of the Example

For the shape ((7,5,4,1)) the generalized hook lengths are exactly the numbers given in the problem statement. Their product is

[ 12 \cdot 11 \cdot 8 \cdot 7 \cdot 5 \cdot 4 \cdot 1 ;\cdot; 9 \cdot 6 \cdot 5 \cdot 3 \cdot 2 ;\cdot; 5 \cdot 4 \cdot 2 \cdot 1 ;\cdot; 1, ]

and the number of shifted SYT of this shape is

[ \frac{17!}{12 \cdot 11 \cdot 8 \cdot 7 \cdot 5 \cdot 4 \cdot 1 \cdot 9 \cdot 6 \cdot 5 \cdot 3 \cdot 2 \cdot 5 \cdot 4 \cdot 2 \cdot 1 \cdot 1}, ]

confirming the formula. (\blacksquare)