Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Hook length formula
Summary
In combinatorial mathematics, the hook length formula is a formula for the number of standard Young tableaux whose shape is a given Young diagram.
It has applications in diverse areas such as representation theory, probability, and algorithm analysis; for example, the problem of longest increasing subsequences. A related formula gives the number of semi-standard Young tableaux, which is a specialization of a Schur polynomial.
Let be a partition of .
It is customary to interpret graphically as a Young diagram, namely a left-justified array of square cells with rows of lengths .
A (standard) Young tableau of shape is a filling of the cells of the Young diagram with all the integers , with no repetition, such that each row and each column form increasing sequences.
For the cell in position , in the th row and th column, the hook is the set of cells such that and or and .
The hook length is the number of cells in .
The hook length formula expresses the number of standard Young tableaux of shape , denoted by or , as
where the product is over all cells of the Young diagram.
The figure on the right shows hook lengths for the cells in the Young diagram , corresponding to the partition 9 = 4 + 3 + 1 + 1. The hook length formula gives the number of standard Young tableaux as:
A Catalan number counts Dyck paths with steps going up (U) interspersed with steps going down (D), such that at each step there are never more preceding D's than U's. These are in bijection with the Young tableaux of shape : a Dyck path corresponds to the tableau whose first row lists the positions of the U-steps, while the second row lists the positions of the D-steps. For example, UUDDUD correspond to the tableaux with rows 125 and 346.
This shows that , so the hook formula specializes to the well-known product formula
There are other formulas for , but the hook length formula is particularly simple and elegant.
A less convenient formula expressing in terms of a determinant was deduced independently by Frobenius and Young in 1900 and 1902 respectively using algebraic methods.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.