§ 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 partitionsuch that the assignment is (a) weakly increasing in the rows, and(b) strictly increasing in the columns. It is strictly increasing in the columnsbecause gravity acts downwards.
  • Formally, a partition is written as λ[λ1,λ2,,λm]\lambda \equiv [\lambda_1, \lambda_2, \dots, \lambda_m], where λi0\lambda_i \geq 0 and iλi=n\sum_i \lambda_i = n, and that theyare weakly decreasing (λ1λ2\lambda_1 \geq \lambda_2 \geq \dots).
  • Formally, to define the tableaux, we first define the diagram dg(λ){(i,j):1jλ[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 bijectionasgn:dg(λ)[n]asgn: dg(\lambda) \rightarrow [n] such that ff is weakly increasing in the rowsand 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
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 numberplaced at 11. But this is wrong, because a young tableaux must be weaklyincreasing 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 arein ascending order. Similarly, the leftover numbers go to the column where thereis 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 lengthformula, we need to fill in for each node the length of the hook, and dividethe full product by n!n!. So forthe hook:
a b c d
This becomes:
6 3 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-leftnumber ought to be the smallest. For the hook HH to be legal, if we distributenumbers into it uniformly at random, then there is a1/(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!={hhook(λ)1/hook-length(h)num(λ)=n!/{hhook(λ)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=irrepRepr(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.