TAOCP 5.1.4 Exercise 38
Let \(T\) be a Young diagram (tableau shape) with \(n = |T|\) cells.
Section 5.1.4: Tableaux and Involutions
Exercise 38. ▶ [M30] (Greene, Nijenhuis, and Wilf, 1979.) We can construct a directed acyclic graph on the cells $T$ of any given tableau shape by letting arcs run from each cell to the other cells in its hook; the out-degree of cell $(i, j)$ will then be $d_{ij} = h_{ij} - 1$, where $h_{ij}$ is the hook length. Suppose we generate a random path in this digraph by choosing a random starting cell $(i, j)$ and choosing further arcs at random, until coming to a corner cell from which there is no exit. Each random choice is made uniformly.
a) Let $(a, b)$ be a corner cell of $T$, and let $I = {i_0, \ldots, i_k}$ and $J = {j_0, \ldots, j_l}$ be sets of rows and columns with $i_0 < \cdots < i_k = a$ and $j_0 < \cdots < j_l = b$. The digraph contains $\binom{k+l}{k}$ paths whose row and column sets are respectively $I$ and $J$; let $P(I, J)$ be the probability that the random path is one of these. Prove that $P(I, J) = 1/(n , d_{i_0 b} \ldots d_{i_{k-1} b} , d_{a j_0} \ldots d_{a j_{l-1}})$, where $n = |T|$.
b) Let $f(T) = n! / \prod h_{ij}$. Prove that the random path ends at corner $(a, b)$ with probability $f(T \setminus {(a, b)})/f(T)$.
c) Show that the result of (b) proves Theorem H and also gives us a way to generate a random tableau of shape $T$, with all $f(T)$ tableaux equally likely.
Verified: yes
Solve time: 44m57s
Setup
Let (T) be a Young diagram (tableau shape) with (n = |T|) cells. For a cell ((i,j) \in T) define its hook as the set of cells ((i, j')) with (j' \ge j) together with ((i', j)) with (i' \ge i). The hook length is (h_{ij} = |\text{hook}(i,j)|). The out‑degree is (d_{ij} = h_{ij} - 1). We build a directed acyclic graph on (T) by putting an arc from ((i,j)) to every other cell in its hook. A random path is generated by:
- choosing a starting cell uniformly from the (n) cells;
- at each step, if the current cell has out‑degree (d > 0), choosing uniformly among the (d) outgoing arcs;
- stopping when a corner cell (out‑degree (0)) is reached.
For a corner ((a,b)) let (I = {i_0 < \dots < i_k = a}) and (J = {j_0 < \dots < j_l = b}) be sets of rows and columns. The path has row set (I) and column set (J) iff it starts at ((i_0,j_0)), uses exactly the rows in (I) and columns in (J), and ends at ((a,b)). Let (P(I,J)) be the probability of this event. Define (f(T) = n! / \prod_{(i,j)\in T} h_{ij}) (with (f(\varnothing)=1)).
(a) Probability of a given row/column set
Because ((a,b)) is a corner, row (a) ends at column (b) and column (b) ends at row (a). Hence for any (i \le a), (j \le b) the cell ((i,j)) belongs to (T). Let (\lambda_i) be the length of row (i) and (\lambda'j) the length of column (j). The hook length is (h{ij} = (\lambda_i - j) + (\lambda'j - i) + 1), so [ d{ij} = h_{ij} - 1 = (\lambda_i - j) + (\lambda'_j - i). ] Since ((a,b)) is a corner, (\lambda_a = b) and (\lambda'b = a). For (i \le a,; j \le b) we obtain the key identity [ d{ij} = (\lambda_i - j) + (\lambda'j - i) = (\lambda_i - b) + (a - i) + (b - j) + (\lambda'j - a) = d{i,b} + d{a,j}. \tag{1} ]
For a fixed interleaving of the (k) down‑moves and (l) right‑moves, the probability of that specific path is [ \frac{1}{n} \prod_{\text{cells } (i,j) \text{ on the path, } (i,j) \ne (a,b)} \frac{1}{d_{ij}}. ] Let (S(I,J)) be the sum of these products over all (\binom{k+l}{k}) interleavings; then (P(I,J) = S(I,J)/n).
We prove by induction on (k+l) that [ S(I,J) = \frac{1}{\prod_{r=0}^{k-1} d_{i_r,b} ; \prod_{s=0}^{l-1} d_{a,j_s}}. \tag{2} ]
Base cases. If (k=0) then (I = {a}) and the unique path moves right through (J); the product is (\prod_{s=0}^{l-1} 1/d_{a,j_s}), matching (2). If (l=0) the unique path moves down and (2) holds similarly.
Inductive step. Assume (2) holds for all smaller (k+l). From ((i_0,j_0)) the first step goes either down to ((i_1,j_0)) or right to ((i_0,j_1)). By the induction hypothesis, [ S(I\setminus{i_0},J) = \frac{1}{\prod_{r=1}^{k-1} d_{i_r,b} \prod_{s=0}^{l-1} d_{a,j_s}}, \qquad S(I,J\setminus{j_0}) = \frac{1}{\prod_{r=0}^{k-1} d_{i_r,b} \prod_{s=1}^{l-1} d_{a,j_s}}. ] Then [ S(I,J) = \frac{1}{d_{i_0,j_0}} \bigl( S(I\setminus{i_0},J) + S(I,J\setminus{j_0}) \bigr). ] Factoring the common denominator and using (1), [ S(I,J) = \frac{1}{d_{i_0,j_0}} \cdot \frac{1}{\prod_{r=1}^{k-1} d_{i_r,b} \prod_{s=1}^{l-1} d_{a,j_s}} \left( \frac{1}{d_{a,j_0}} + \frac{1}{d_{i_0,b}} \right) = \frac{1}{d_{i_0,j_0}} \cdot \frac{1}{\prod_{r=1}^{k-1} d_{i_r,b} \prod_{s=1}^{l-1} d_{a,j_s}} \cdot \frac{d_{i_0,j_0}}{d_{i_0,b} d_{a,j_0}}, ] which simplifies to (2). Hence [ P(I,J) = \frac{1}{n \prod_{r=0}^{k-1} d_{i_r,b} \prod_{s=0}^{l-1} d_{a,j_s}}. ]
(b) Probability of ending at a given corner
The path ends at ((a,b)) exactly when its row set (I) and column set (J) satisfy (\max I = a), (\max J = b). Every subset (I \subseteq {1,\dots,a}) containing (a) and (J \subseteq {1,\dots,b}) containing (b) is valid because (T) is a Young diagram. Summing (P(I,J)) over all such (I,J) gives [ \frac{1}{n} \left( \sum_{I \ni a} \prod_{\substack{i\in I\ i<a}} \frac{1}{d_{i,b}} \right) \left( \sum_{J \ni b} \prod_{\substack{j\in J\ j<b}} \frac{1}{d_{a,j}} \right) = \frac{1}{n} \prod_{i=1}^{a-1} \left(1 + \frac{1}{d_{i,b}}\right) \prod_{j=1}^{b-1} \left(1 + \frac{1}{d_{a,j}}\right). \tag{3} ]
Removing the corner ((a,b)) from (T) reduces the hook length by (1) for each cell in row (a) (columns (<b)) and in column (b) (rows (<a)); other hook lengths are unchanged. Since (d_{ij} = h_{ij}-1), the new hook lengths of ((a,j)) and ((i,b)) become (d_{a,j}) and (d_{i,b}) respectively. Therefore [ \frac{f(T\setminus{(a,b)})}{f(T)} = \frac{(n-1)! / \prod_{T\setminus{(a,b)}} h'}{n! / \prod_T h} = \frac{1}{n} \prod_{i=1}^{a-1} \frac{h_{i,b}}{h_{i,b}-1} \prod_{j=1}^{b-1} \frac{h_{a,j}}{h_{a,j}-1} = \frac{1}{n} \prod_{i=1}^{a-1} \left(1 + \frac{1}{d_{i,b}}\right) \prod_{j=1}^{b-1} \left(1 + \frac{1}{d_{a,j}}\right). ] This is exactly (3). Hence the probability that the random path ends at ((a,b)) equals (f(T\setminus{(a,b)})/f(T)).
(c) Proof of Theorem H and random tableau generation
Theorem H states that the number of standard Young tableaux of shape (T) is (f(T)). Consider the following algorithm:
- Set (T_n = T).
- For (k = n, n-1, \dots, 1):
- Run the random path on the current shape (T_k).
- Let ((a,b)) be the corner where it stops.
- Place the number (k) in cell ((a,b)).
- Set (T_{k-1} = T_k \setminus {(a,b)}).
By part (b), at step (k) the probability of choosing corner ((a,b)) is (f(T_{k-1})/f(T_k)). The probability of a specific sequence of corners ((c_n, c_{n-1}, \dots, c_1)) is [ \prod_{k=1}^n \frac{f(T_{k-1})}{f(T_k)} = \frac{f(T_0)}{f(T_n)} = \frac{1}{f(T)}, ] because (T_0 = \varnothing) and (f(\varnothing)=1). Each such sequence corresponds uniquely to a standard Young tableau (by putting (k) in the cell removed at step (k)), and every standard Young tableau yields exactly one such sequence by repeatedly removing its largest entry. Thus the algorithm produces each of the (f(T)) standard Young tableaux with equal probability (1/f(T)). Since the total probability sums to (1), there are exactly (f(T)) tableaux. This proves Theorem H and simultaneously provides a method to generate a uniformly random standard Young tableau of shape (T). ∎