TAOCP 5.1.4 Exercise 36

Section 5.1.4: Tableaux and Involutions

Exercise 36. [HM27] (R. P. Stanley, 1971.) (a) Prove that the number of reverse plane partitions of $m$ in a given shape is $\lfloor s^m \rfloor / \prod (1 - z^{h_{ij}})$, where the numbers $h_{ij}$ are the hook lengths of the shape. (b) Derive Theorem H from this result. [Hint: What is the asymptotic number of partitions as $m \to \infty$?]

Verified: yes
Solve time: 1h02m

Solution

Let (\lambda) be a fixed Young diagram with (n) cells. A reverse plane partition (RPP) of shape (\lambda) is an array (p = (p_{ij}){(i,j)\in\lambda}) of nonnegative integers such that rows and columns are weakly increasing: [ p{ij} \le p_{i,j+1},\qquad p_{ij} \le p_{i+1,j} ] (where missing neighbours are ignored). The sum of (p) is (m = \sum p_{ij}). The hook length (h_{ij}) of cell ((i,j)) is the number of cells in its hook (the cell itself, all cells to its right in the same row, and all cells below it in the same column).

(a) Generating function for reverse plane partitions

We construct a bijection between RPPs of shape (\lambda) and tuples of nonnegative integers indexed by the cells. For each cell ((i,j)) define [ a_{ij} = p_{ij} - \max(p_{i-1,j},, p_{i,j-1}), ] with the convention (p_{0,j}=p_{i,0}=0). Because rows and columns are weakly increasing, (a_{ij} \ge 0). The map (p \mapsto a) is invertible: given (a_{ij}\ge 0) we recover (p_{ij}) recursively by [ p_{ij} = \max(p_{i-1,j},, p_{i,j-1}) + a_{ij}, ] processing the cells in any order compatible with the partial order (e.g., row by row, left to right). Hence there is a bijection between RPPs and sequences ((a_{ij})) of nonnegative integers.

Now express the sum (m = \sum p_{ij}) in terms of the (a_{ij}). Observe that each (p_{ij}) appears in the definition of (a_{kl}) exactly when ((k,l)) belongs to the hook of ((i,j)). More formally, one can prove by induction on the hook that [ p_{ij} = \sum_{(k,l)\in \text{hook}(i,j)} a_{kl}. ] Summing over all cells gives [ \sum p_{ij} = \sum_{i,j} h_{ij}, a_{ij}. ]

Therefore the ordinary generating function for RPPs by sum is [ \sum_{\text{RPP }p} z^{\sum p_{ij}} = \sum_{a_{ij}\ge 0} z^{\sum h_{ij}a_{ij}} = \prod_{i,j} \left(\sum_{a=0}^\infty z^{h_{ij}a}\right) = \prod_{i,j} \frac{1}{1 - z^{h_{ij}}}. ] The number of RPPs of sum (m) is the coefficient of (z^m) in this product, i.e. [ [z^m] \prod_{i,j} \frac{1}{1 - z^{h_{ij}}}. ]

(b) Derivation of the hook‑length formula (Theorem H)

Theorem H states that the number (f^\lambda) of standard Young tableaux of shape (\lambda) is [ f^\lambda = \frac{n!}{\prod_{i,j} h_{ij}}. ]

Let (p_\lambda(m)) denote the number of RPPs of shape (\lambda) with sum (m). We will compute the asymptotic behaviour of (p_\lambda(m)) as (m\to\infty) in two different ways and equate the leading terms.

First asymptotic (from the generating function)

As (z\to 1), we have (1 - z^{h_{ij}} \sim h_{ij}(1-z)). Hence [ \prod_{i,j} \frac{1}{1 - z^{h_{ij}}} \sim \frac{1}{\prod h_{ij}}; \frac{1}{(1-z)^n}. ] The coefficient of (z^m) in ((1-z)^{-n}) is (\binom{m+n-1}{n-1} = \frac{m^{n-1}}{(n-1)!} + O(m^{n-2})). Therefore [ p_\lambda(m) \sim \frac{1}{\prod h_{ij}}; \frac{m^{n-1}}{(n-1)!}. \tag{1} ]

Second asymptotic (double counting with standard Young tableaux)

A standard Young tableau (SYT) of shape (\lambda) is a bijection (T : \lambda \to {1,\dots,n}) that is strictly increasing along rows and columns. For a given RPP (p), we say that an SYT (T) is compatible with (p) if the values of (p) are nondecreasing when the cells are read in the order of (T): [ p\bigl(T^{-1}(1)\bigr) \le p\bigl(T^{-1}(2)\bigr) \le \cdots \le p\bigl(T^{-1}(n)\bigr). ]

We count the number of pairs ((p,T)) where (p) is an RPP of sum (m) and (T) is an SYT compatible with (p).

Counting by first choosing (T):
Fix an SYT (T). The condition “(p) is compatible with (T)” means that the sequence (a_i = p(T^{-1}(i))) satisfies (0 \le a_1 \le a_2 \le \cdots \le a_n) and (\sum a_i = m). The number of such sequences is the coefficient of (z^m) in [ \prod_{i=1}^n \frac{1}{1 - z^i}. ] As (z\to 1), (\prod_{i=1}^n (1-z^i)^{-1} \sim \frac{1}{n!}(1-z)^{-n}), so the coefficient is [ \frac{m^{n-1}}{(n-1)!,n!} + O(m^{n-2}). ] Summing over all (f^\lambda) SYTs gives [ #{(p,T)} = f^\lambda \left( \frac{m^{n-1}}{(n-1)!,n!} + O(m^{n-2}) \right). \tag{2} ]

Counting by first choosing (p):
For a fixed RPP (p), the compatible SYTs are exactly the linear extensions of the poset obtained by adding the relation (u < v) whenever (p(u) < p(v)). If all values (p(u)) are distinct, this poset is a total order, so there is exactly one compatible SYT. If some values coincide, the poset is not totally ordered and there may be several compatible SYTs. However, the number of RPPs that have at least one equality (p(u)=p(v)) ((u\ne v)) is (O(m^{n-2})). Indeed, each such equality forces the point ((p_{ij})) to lie on a hyperplane inside the cone of all weakly increasing arrays; this reduces the dimension of the solution set by one, so the number of integer points with sum (m) is (O(m^{n-2})). There are only finitely many pairs of cells, so the union over all equalities is still (O(m^{n-2})).

Thus for almost all RPPs there is exactly one compatible SYT, and the exceptional set contributes only to the error term. Hence the total number of pairs ((p,T)) is asymptotically equal to the total number of RPPs: [ #{(p,T)} = p_\lambda(m) + O(m^{n-2}). \tag{3} ]

Equating the asymptotics

From (1) we have (p_\lambda(m) \sim \frac{1}{\prod h_{ij}}\frac{m^{n-1}}{(n-1)!}). Substituting into (3) and comparing with (2) gives [ f^\lambda \cdot \frac{m^{n-1}}{(n-1)!,n!} ;\sim; \frac{1}{\prod h_{ij}} \cdot \frac{m^{n-1}}{(n-1)!}. ] Cancelling the common factor (\frac{m^{n-1}}{(n-1)!}) yields [ \frac{f^\lambda}{n!} = \frac{1}{\prod h_{ij}}, ] i.e. [ \boxed{f^\lambda = \frac{n!}{\prod_{i,j} h_{ij}}}. ] This is the hook‑length formula (Theorem H). ∎