Hook length formula

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.

The hook length formula expresses the number of standard Young tableaux of shape

The figure on the right shows hook lengths for the cells in the Young diagram

in terms of a determinant was deduced independently by Frobenius and Young in 1900 and 1902 respectively using algebraic methods.

[1][2] MacMahon found an alternate proof for the Young–Frobenius formula in 1916 using difference methods.

Discussing the work of Staal (a student of Robinson), Frame was led to conjecture the hook formula.

At first Robinson could not believe that such a simple formula existed, but after trying some examples he became convinced, and together they proved the identity.

On Saturday they went to the University of Michigan, where Frame presented their new result after a lecture by Robinson.

The search for a short, intuitive explanation befitting such a simple result gave rise to many alternate proofs.

[5] Hillman and Grassl gave the first proof that illuminates the role of hooks in 1976 by proving a special case of the Stanley hook-content formula, which is known to imply the hook length formula.

[10] A simpler direct bijection was announced by Pak and Stoyanovskii in 1992, and its complete proof was presented by the pair and Novelli in 1997.

R. M. Thrall found the analogue to the hook length formula for shifted Young Tableaux in 1952.

The hook length formula can be understood intuitively using the following heuristic, but incorrect, argument suggested by D. E.

Knuth's argument is however correct for the enumeration of labellings on trees satisfying monotonicity properties analogous to those of a Young tableau.

occurs at one of its corner cells, so deleting it gives a Young tableaux of shape

The hook length formula is of great importance in the representation theory of the symmetric group

The above equality can be proven also checking the coefficients of each monomial at both sides and using the Robinson–Schensted–Knuth correspondence or, more conceptually, looking at the decomposition of

is the hook length of the first box in each row of the Young diagram, and this expression is easily transformed into the desired form

The hook length formula also has important applications to the analysis of longest increasing subsequences in random permutations.

, Anatoly Vershik and Sergei Kerov[18] and independently Benjamin F. Logan and Lawrence A. Shepp[19] showed that when

The proof is based on translating the question via the Robinson–Schensted correspondence to a problem about the limiting shape of a random Young tableau chosen according to Plancherel measure.

, the hook length formula can then be used to perform an asymptotic analysis of the limit shape and thereby also answer the original question.

The ideas of Vershik–Kerov and Logan–Shepp were later refined by Jinho Baik, Percy Deift and Kurt Johansson, who were able to achieve a much more precise analysis of the limiting behavior of the maximal increasing subsequence length, proving an important result now known as the Baik–Deift–Johansson theorem.

was originally derived from the Frobenius determinant formula in connection to representation theory:[20] Hook lengths can also be used to give a product representation to the generating function for the number of reverse plane partitions of a given shape.

[21] If λ is a partition of some integer p, a reverse plane partition of n with shape λ is obtained by filling in the boxes in the Young diagram with non-negative integers such that the entries add to n and are non-decreasing along each row and down each column.

, we are considering the poset in its cells given by the relation So a linear extension is simply a standard Young tableau, i.e.

Combining the two formulas for the generating functions we have Both sides converge inside the disk of radius one and the following expression makes sense for

gives the number of semi-standard tableaux, which can be written in terms of hook lengths:

We may refine this by taking the principal specialization of the Schur function in the variables