§ Hook length formula

Truly remarkable formula that tells us the number of standard young tableaux for a given partition $\lambda$ of $n$. Recall the definitions:

• A partition $\lambda$ of the number $n$.
• An assignment of numbers $\{1, 2, \dots n\}$ onto the diagram of the partition such that the assignment is (a) weakly increasing in the rows, and (b) strictly increasing in the columns. It is strictly increasing in the columns because gravity acts downwards.
• Formally, a partition is written as $\lambda \equiv [\lambda_1, \lambda_2, \dots, \lambda_m]$, where $\lambda_i \geq 0$ and $\sum_i \lambda_i = n$, and that they are weakly decreasing ( $\lambda_1 \geq \lambda_2 \geq \dots$).
• Formally, to define the tableaux, we first define the diagram $dg(\lambda) \equiv \{ (i, j) : 1 \leq j \leq \lambda[i] \}$which are the "locations" of the cells when visualizing $\lambda$ as a Ferrers diagram.
• Finally, the actual assignment of the numbers to the tableaux is given by a bijection $asgn: dg(\lambda) \rightarrow [n]$ such that $f$ is weakly increasing in the rows and strictly increasing in the columns.

§ The formula

Now, we want to count the number of young tableaux (formally, the data $n, \lambda, asgn$) for a given partition $\lambda$. The formula is:

where $hooklen$ is the largest "hook shape":

* * *
*
*
...

at the cell $(i, j)$ that is in the partition $\lambda$.

§ The structure of hooks

say we have a hook shape

a b c d
e
f

And the numbers $\{1, 2, 3, 4, 5, 6\}$. How many ways can we assign the numbers to the above hook shape such that its a legal young tableaux?

• First, see that $a = 1$ is a must. Proof by contradiction. Assume $1$is not placed at $a$. Whenever it is placed, it will be less than the number placed at $1$. But this is wrong, because a young tableaux must be weakly increasing in the rows and strictly increasing in the columns.
• Next, see that after placing $a = 1$, the other numbers can be placed "freely": If we take a subset of $\{2, 3, 4, 5, 6\}$ of the size of the leftover row, ie, $|b~c~d| = 3$, then there is only one way to place them such that they are in ascending order. Similarly, the leftover numbers go to the column where there is only one way to place them.
• Hence, after $a = 1$ is fixed, for every $5C3$ subset, we get a legal hook.
• In general, if we have $n=r+c+1$ nodes, with $r+1$ nodes in the row, and $c+1$nodes in the column (the top-left node is counted twice), then we have $\binom{r+c}{r}$number of legal hooks; Once we pick the lowest number for the top left node, every $r$-subset will give us a hook.

• This result matches the hook-length formula. According to the hook length formula, we need to fill in for each node the length of the hook, and divide the full product by $n!$. So for the hook:

a b c d
e
f

This becomes:

6 3 2 1
2
1

where $r=3, c=2$.

§ Knuth's heuristic

• Consider the hook shape. The only constraint we have is that the top-left number ought to be the smallest. For the hook $H$ to be legal, if we distribute numbers into it uniformly at random, then there is a $1/(\texttt{hook-length}(H))$ probability that the hook will be legal.

• The tableaux will be legal iff all the hooks in the tableaux are legal

• Thus, the probability of getting a legal tableaux is:

§ The relationship to representation theory

The RSK correspondence gives us a bijection between the permutation group $S_n$ and pairs of standard young tableaux:

given by the pair of insertion tableaux and the recording tableaux for each partition $\lambda$ of $n$.
If we look at this in terms of set sizes, then it tells us that:

This looks very suspicious, almost like the representation theoretic formula of:

and it is indeed true that $\texttt{hook-length-formula}(\lambda)$ corresponds to the dimension of an irreducible representation of $S_n$, and each $\lambda$ corresponds to an irrep of $S_n$.