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 λ = {λ1,λ2,…,λm} be a partition of n. That is, λ1,λ2,…,λm are positive integers such that n = λ1 + λ2 + … + λm and λ1 ≥ λ2 ≥ … ≥ λ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 of shape λ in which each of the n cells contains a distinct integer between 1 and n (i.e., no repetition), such that each row and each column form increasing sequences. For each cell (i,j) of Y(λ), 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). [1]
Then the hook-length formula is
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 a less convenient determinant formula for dλ. [2] This earlier formula was deduced independently by G. Frobenius and A. Young in 1900 and 1902 respectively using algebraic methods. [3] [4] P. A. MacMahon found an alternate proof for the Young-Frobenius formula in 1916 using difference methods. [5]
Since its discovery in 1954, many alternate proofs for the hook-length have been found. C. Greene, A. Nijenhuis, and H. S. Wilf found a probabilistic proof in which the hook lengths appear naturally in 1979. [6] A direct bijective proof was first discovered by D. S. Franzblau and D. Zeilberger in 1982. [7] A simpler bijective proof was announced by Igor Pak and Alexander V. Stoyanovskii in 1992, and it was fully proven by the pair and Jean-Christophe Novelli in 1997. [8] [9]
References
- ^ Greene, C., Nijenhuis, A. and Wilf, H. S. (1979). A probabilistic proof of a formula for the number of Young tableaux of a given shape. Adv. in Math. 31, 104–109.
- ^ Frame, J. S., Robinson, G. de B. and Thrall, R. M. (1954). The hook graphs of the symmetric group. Canad. J. Math. 6, 316–325.
- ^ G. FROBENIUS, Uber die charaktere der symmetrischer gruppe, Preuss. &ad. Wk. sitz. (1900), 516-534.
- ^ A. YOUNG, Quantitative substitutional analysis II, Proc. London Math. Sot., Ser. 1, 35 (1902), 361-397.
- ^ P. A. MACMAHON, “Combinatory Analysis,” Cambridge Univ. Press, London/New York, 1916; reprinted by Chelsea, New York, 1960.
- ^ Greene, C., Nijenhuis, A. and Wilf, H. S. (1979). A probabilistic proof of a formula for the number of Young tableaux of a given shape. Adv. in Math. 31, 104–109.
- ^ Franzblau, D. S. and Zeilberger, D. (1982). A bijective proof of the hook-length formula. J. Algorithms 3, 317–343.
- ^ Pak, I. M. and Stoyanovskii, A. V. (1992). A bijective proof of the hook-length formula. Funct. Anal. Appl. 24.
- ^ Novelli, J.-C., Pak, I. M. and Stoyanovskii, A. V. (1997). A direct bijective proof of the hook-length formula. Discrete Mathematics and Theoretical Computer Science 1, 1997, 53–67.
Stanley 1972 Hillman and Grassl provided in 1976 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.
For the latter, the bijection without the complete proof was announced in 1992 by presented its proof was fully preseneted complete proof was presented