hook length formula

Statement

Let $f_{λ}$ be the number of standard Young tableaux of shape $λ$ (a partition). Let $h (b)$ for $b \in λ$ be the hook length. Then,

f_{λ} = \frac{n!}{\prod_{b \in λ} h (b)}

As notation, let $H (λ) = \prod_{b \in λ} h (b)$ .

This was proven by Frame-Robinson-Thrall in 1953.

Proof

We give the "Hook walk" proof by Greene-Nijenhuis-Wilf (1979). The intuition is as follows:

There is a recurrence relationship that $f_{λ}$ satisfies:

f_{λ} = \sum_{c corner} f_{λ ∖ c}

Where a corner box is defined to be the boxes with hook length 1 (ie. there are no boxes below or to the right of it). We note that the largest number of the tableaux must be in a corner box. If the largest number is in some corner box $c$ , then we can fill in the rest of the diagram ( $λ ∖ c$ ) in $f_{λ ∖ c}$ ways. Then, we sum over all corner boxes.

It then suffices to show that the RHS also satisfies the recurrence relation. In other words, we need to show

\frac{n!}{H (λ)} = \sum_{c corner} \frac{(n - 1)!}{H (λ ∖ c)}

which is equivalent to showing that

\sum_{c corner} \frac{1}{n} \cdot \frac{H (λ)}{H (λ ∖ c)} = 1

We shall do so by viewing this as a probability measure. In particular, we want to show that $\frac{1}{n} \cdot \frac{H (λ)}{H (λ ∖ c)}$ is the probability of something depending on $c$ .

Consider the random process (which we shall call a Hook walk):

Randomly select a box $b_{1} \in λ$ (so each box has a probability of $\frac{1}{n}$ of being selected)
Repeat for $i \geq 1$ : starting from $b_{i}$ , pick $b_{i + 1}$ in the hook of $b_{i}$ (that is not $b_{i}$ )
Note that the above process terminates once we reach a corner box $c$ . Output this $c$ .
Example:

We want to ask about the probability that this hook walk ends at some corner $c$ , which we shall denote as $P (c)$ . We note that this is equal to:

P (c) = \sum_{b_{1} \to b_{2} \to \dots \to b_{r} = c} \frac{1}{n} \cdot \frac{1}{h (b_{1}) - 1} \cdot \frac{1}{h (b_{2}) - 1} \cdot \dots \cdot \frac{1}{h (b_{r - 1}) - 1}

where we take the sum over all hook walks that end at $c$ . So, it suffices to show that

\frac{1}{n} \cdot \frac{H (λ)}{H (λ ∖ c)} = \sum_{b_{1} \to b_{2} \to \dots \to b_{r} = c} \frac{1}{n} \cdot \frac{1}{h (b_{1}) - 1} \cdot \frac{1}{h (b_{2}) - 1} \cdot \dots \cdot \frac{1}{h (b_{r - 1}) - 1}

First, we note that any hook walk that ends at $c$ must lie in the rectangle $R$ with vertices cut out by $(1, 1)$ and $c$ :

For any box $a \in R$ , we can find $b, d$ such that we have a rectangle with the boxes $a b c d$ .

Furthermore, let the cohook be the boxes that are above and to the left of a box. Note that $b, d$ lie in the cohook of $c$ .
20260211_133307 (1).jpg

We further note that

\begin{aligned} h (a) + h (c) & = h (b) + h (d) \\ h (a) - 1 & = h (b) - 1 + h (d) - 1 \end{aligned}

The second line obtained by subtracting one from both sides and noticing that $h (c) = 1$ . This means in particular that the hook length of any box within the rectangle is determined by the hook length on the sides.

Let $R$ have side lengths $(k + 1) \times (l + 1)$ and for each box $b$ in this rectangle, associate it with the weight $h (b) - 1$ . We shall say that the weight of a hook walk is the product of all the weights of the boxes that are in the hook walk. Furthermore, label the boxes in the cohook of $c$ with $x_{1}, \dots, x_{k}$ (with $x_{i}$ being the box in position $(i, l + 1)$ , the vertical line) and $y_{1}, \dots, y_{l}$ (with $y_{i}$ being in the box $(k + 1, i)$ , the horizontal line).
This in particular means that the weight of any box is $\frac{1}{x_{i} + y_{j}}$ if they are in the $i$ th row and the $j$ th column.

Here is a simple example of the weight of a path:

Lemma: Define a lattice path to be a Hook walk that is connected. We claim that

\sum_{p lattice path in R} wt (P) = \frac{1}{x_{1} \dots x_{k} y_{1} \dots y_{l}}

We proof via induction on $k + l$ (in particular, note that the base case will be the $n \times 1$ and the $1 \times n$ strip, which is not too hard). For the inductive case, let $a^{'}$ be the box directly to the right of $a = (1, 1)$ , and $a^{″}$ be the box directly below $a$ . We have the recurrence:

\begin{aligned} \sum_{p : a \to c} wt (P) & = \frac{1}{x_{1} + y_{1}} (\sum_{p^{'} : a^{'} \to c} wt (p^{'}) + \sum_{p^{″} : a^{″} \to c} wt (p^{″})) \\ = \frac{1}{x_{1} + y_{1}} (\frac{1}{x_{1} \dots x_{k} y_{2} \dots y_{l}} + \frac{1}{x_{2} \dots x_{k} y_{1} \dots y_{l}}) \\ = \frac{1}{x_{1} \dots x_{k} y_{1} \dots y_{l}} \end{aligned}

Now we can apply this lemma to prove the same formula for a general hook walk:
For every box, we mark down the rows and columns that it occupies. This creates a subgrid, and within this subgrid, we have a lattice path. We may then apply the lemma to get

\begin{aligned} \sum_{p hook walk in R} wt (P) & = \sum_{I \subset [k], J \subset [l]} \frac{1}{\prod_{i \in I} x_{i} \prod_{j \in J} y_{j}} \\ = \prod_{i = 1}^{k} (1 + \frac{1}{x_{i}}) \prod_{j = 1}^{l} (1 + \frac{1}{y_{l}}) \end{aligned}

So in general, we have the formula for the probability that a hook walk will end at $c$ :

\begin{aligned} P (c) & = \frac{1}{n} \prod_{i = 1}^{k} (1 + \frac{1}{x_{i}}) \prod_{j = 1}^{l} (1 + \frac{1}{y_{l}}) \\ = \frac{1}{n} \prod_{b \in cohook (c), b \neq c} (1 + \frac{1}{h (b) - 1}) \\ = \frac{1}{n} \prod_{b \in cohook (c), b \neq c} \frac{h (b)}{h (b) - 1} \end{aligned}

We claim that this is equal to $\frac{1}{n} \frac{H (λ)}{H (λ ∖ c)}$ as we note that for $b$ not in the cohook, then removing $c$ does not change the hook length of $b$ , so they cancel out. If $b$ is in the cohook, then that cohook gets reduced by 1.

Thus, we have shown that the quantity is a probability measure, and so if we take the sum over all possible corners, we must get 1.