§ Hook length formula

Truly remarkable formula that tells us the number of standard young tableaux for a given partition λ\lambda of nn. Recall the definitions:
  • A partition λ\lambda of the number nn.
  • An assignment of numbers {1,2,…n}\{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 λ≡[λ1,λ2,…,λm]\lambda \equiv [\lambda_1, \lambda_2, \dots, \lambda_m], where λi≥0\lambda_i \geq 0 and ∑iλi=n\sum_i \lambda_i = n, and that they are weakly decreasing ( λ1≥λ2≥…\lambda_1 \geq \lambda_2 \geq \dots).
  • Formally, to define the tableaux, we first define the diagram dg(λ)≡{(i,j):1≤j≤λ[i]}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(λ)→[n]asgn: dg(\lambda) \rightarrow [n] such that ff 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,λ,asgnn, \lambda, asgn) for a given partition λ\lambda. The formula is:
n!/(∏cell∈λhooklen(cell)) n!/\left(\prod_{\texttt{cell} \in \lambda} hooklen(\texttt{cell})\right)
where hooklenhooklen is the largest "hook shape": 
* * *
*
*
...
at the cell (i,j)(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}\{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=1a = 1 is a must. Proof by contradiction. Assume 11is not placed at aa. Whenever it is placed, it will be less than the number placed at 11. 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=1a = 1, the other numbers can be placed "freely": If we take a subset of {2,3,4,5,6}\{2, 3, 4, 5, 6\} of the size of the leftover row, ie, ∣b c d∣=3|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=1a = 1 is fixed, for every 5C35C3 subset, we get a legal hook.
  • In general, if we have n=r+c+1n=r+c+1 nodes, with r+1r+1 nodes in the row, and c+1c+1nodes in the column (the top-left node is counted twice), then we have (r+cr)\binom{r+c}{r}number of legal hooks; Once we pick the lowest number for the top left node, every rr-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!n!. So for the hook: 
a b c d
e
f
This becomes: 
6 3 2 1
2
1
6!/(6×3!×2!)=5!/(3!2!)=5C3=(r+cr) 6!/(6\times 3!\times 2!) = 5!/(3! 2!) = 5C3 = \binom{r+c}{r}
where r=3,c=2r=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 HH to be legal, if we distribute numbers into it uniformly at random, then there is a 1/(hook-length(H))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:
num(λ)/n!=∏{h∈hook(λ)1/hook-length(h)num(λ)=n!/∏{h∈hook(λ)hook-length(h) \begin{aligned} &\texttt{num}(\lambda)/n! = \prod_\{h \in \texttt{hook}(\lambda) 1/\texttt{hook-length}(h) \\ &\texttt{num}(\lambda) = n!/\prod_\{h \in \texttt{hook}(\lambda)\texttt{hook-length}(h) \\ \end{aligned}

§ The relationship to representation theory

The RSK correspondence gives us a bijection between the permutation group SnS_n and pairs of standard young tableaux:
RSK≡⋃λ∈partition(n)SYT(λ)×SYT(λ) RSK \equiv \bigcup_{\lambda \in \texttt{partition}(n)} SYT(\lambda) \times SYT(\lambda)
given by the pair of insertion tableaux and the recording tableaux for each partition λ\lambda of nn. If we look at this in terms of set sizes, then it tells us that:
∣Sn∣=∣⋃λ∈partition(n)SYT(λ)×SYT(λ)n!=∑λ∈partition(n)∣SYT(λ)∣2n!=∑λ∈partition(n)∣hook-length-formula(λ)∣2 \begin{aligned} &|S_n| = |\bigcup_{\lambda \in \texttt{partition}(n)} SYT(\lambda) \times SYT(\lambda) \\ &n! = \sum_{\lambda \in \texttt{partition}(n)} |SYT(\lambda)|^2 \\ &n! = \sum_{\lambda \in \texttt{partition}(n)} |\texttt{hook-length-formula}(\lambda)|^2 \\ \end{aligned}
This looks very suspicious, almost like the representation theoretic formula of:
group-size=∑irrep∈Repr(G)dim(irrep)2 \texttt{group-size} = \sum_{\texttt{irrep} \in Repr(G)} dim(\texttt{irrep})^2
and it is indeed true that hook-length-formula(λ)\texttt{hook-length-formula}(\lambda) corresponds to the dimension of an irreducible representation of SnS_n, and each λ\lambda corresponds to an irrep of SnS_n.