User:TestFunction/sandbox

In combinatorial mathematics, the hook-length formula gives d_λ, the number of Young tableau of shape λ, as a function of the hook-lengths of λ. It has applications to representation theory and the problem of longest increasing subsequences.

Let λ = {λ₁,λ₂,…,λ_m} be a partition of n. That is, λ₁,λ₂,…,λ_m are positive integers such that n = λ₁ + λ₂ + … + λ_m and λ₁ ≥ λ₂ ≥ … ≥ λ_m. Then the Young diagram of shape λ, denoted Y(λ), is an array of cells with indices (i,j) where 1 ≤ i ≤ m and 1 ≤ j ≤ λ_i. The Young diagram of shape λ has n cells and has a natural bijection to a partition of n. A standard Young tableau of shape λ is a Young diagram with an integer between 1 and n in each cell without repetition such that each row and each column form increasing sequences. For each cell (i,j) of λ, the hook H_λ(i,j) is the set of all cells (a,b) such that a=i and b≥j or a≥i and b=j. The hook-length h_λ(i,j) is defined as |H_λ(i,j)|, the number of cells in the hook H_λ(i,j).

Then the hook-length formula is

$d_{\lambda }={\frac {n!}{\prod _{(i,j)\in Y(\lambda )}\mathrm {h_{\lambda }} (i,j)}}.$

There are other formulas for d_λ, but the hook-length formula is particularly simple. Indeed, the hook-length formula was discovered in 1954 by J. S. Frame, G. de B. Robinson, and R. M. Thrall by improving an earlier, less convenient determinant formula for d_λ, which was deduced independently by G. Frobenius and A. Young in 1900 and 1902 respectively using algebraic methods. P. A. MacMahon found an alternate proof for the Young-Frobenius formula in 1916 using difference methods.

Since its discovery in 1954, many alternate proofs for the hook-length have been found. Hillman and Grassl provided in 1976 a combinatorial “explanation” of hooks in ????to date. Their proof uses hooks in a natural way to derive a combinatorial correspondence involving plane partitions, from which the Frame-Robinson-Thrall formula can be derived by an asymptotic argument. Greene, Nijenhuis, and Wilf found a probabilistic proof in which the hook lengths appear naturally in 1979. A direct bijective proof was first discovered by Franzblau and Zeilberger in 1982, and a simpler bijective proof was presented by Novelli-Pak-Stoyanovskii in 1997.

For each cell (i,j) of λ, the hook H_λ(i,j) is {(a,b): a=i and b≥j or a≥i and b=j}.

Young diagram with a distinct integer between 1 and n in each cell Young diagram with an integer between 1 and n in each cell without repetition