§ Hook length formula
Truly remarkable formula that tells us the number of standard young tableaux
for a given partition of . Recall the definitions:
- A partition of the number .
- An assignment of numbers 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 , where and , and that they are weakly decreasing ( ).
- Formally, to define the tableaux, we first define the diagram which are the "locations" of the cells when visualizing as a Ferrers diagram.
- Finally, the actual assignment of the numbers to the tableaux is given by a bijection such that 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 )
for a given partition . The formula is:
where is the largest "hook shape":
at the cell that is in the partition .
* * *
§ The structure of hooks
say we have a hook shape
And the numbers . How many ways can we assign the numbers
to the above hook shape such that its a legal young tableaux?
a b c d
- First, see that is a must. Proof by contradiction. Assume is not placed at . Whenever it is placed, it will be less than the number placed at . 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 , the other numbers can be placed "freely": If we take a subset of of the size of the leftover row, ie, , 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 is fixed, for every subset, we get a legal hook.
- In general, if we have nodes, with nodes in the row, and nodes in the column (the top-left node is counted twice), then we have number of legal hooks; Once we pick the lowest number for the top left node, every -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 . So for the hook:
a b c d
6 3 2 1
§ 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 to be legal, if we distribute numbers into it uniformly at random, then there is a 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
and pairs of standard young tableaux:
given by the pair of insertion tableaux and the recording tableaux for each partition
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 corresponds
to the dimension of an irreducible representation of , and each
corresponds to an irrep of .