User:TestFunction/sandbox

This is the user sandbox of TestFunction. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.

Other sandboxes: Main sandbox | Template sandbox

Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

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 many proofs and has been extended in several different ways. Applications have been found in probability, algebraic geometry, group theory, representation theory, and algorithm analysis, for example 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 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

d_{\lambda }={\frac {n!}{\prod _{(i,j)\in Y(\lambda )}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 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 formula have been found, particularly because no simple proof has been found despite/for such a simple result. (cite Knuth) (( in the quest for a shorter and more intuitive proof. Despite the simplicity of the hook-length formula, initially it was not clear why hooks appeared in the formula. )) Hillman and Grassl gave the first proof that illuminates the role of hooks in 1976 (via a combinatorial bijection). They proved a special case of the Stanley hook-content formula, which is known to imply the hook-length formula. Inspired by this result, 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 its complete proof was presented by the pair and Jean-Christophe Novelli in 1997. ^[8] ^[9]

Meanwhile, the hook-length formula has been generalized and extended in several different ways. Sagan and Yeh found and proved hook-length formulas for shifted Young Tableaux and binary trees.

((The first bijective proof was found by Remmel in 1982 (but isn't prob proof also bijective?)) It has been reproved, generalized and extended in several different ways, and applications have been found in a number of fields ranging from algebraic geometry to probability, and from group theory to the analysis of algorithms. Still, the hook length formula remains deeply mysterious and its full depth is yet to be completely understood. Applications include representation theory and the problem of longest increasing subsequences.

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.

Since then, it has been reproved, generalized and extended in several different ways. Applications have been found in a number of fields ranging from algebraic geometry to probability, and from group theory to the analysis of algorithms. Still, the hook length formula remains deeply mysterious and its full depth is yet to be completely understood.

Knuth wrote in 1973, “Since the hook-lengths formula is such a simple result, it deserves a simple proof ...”

since then there were many attempts to find a simpler proof (simplify proof)

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.

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 fully proven its proof was fully preseneted complete proof was presented

In combinatorial mathematics, the hook-length formula is … (a few paragraphs explaining what it's about, who proved it and when).

[1] 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.

[2] 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.

[3] G. Frobenius, Uber die charaktere der symmetrischer gruppe, Preuss. &ad. Wk. sitz. (1900), 516-534.

[4] A. Young, Quantitative substitutional analysis II, Proc. London Math. Sot., Ser. 1, 35 (1902), 361-397.

[5] P. A. MacMahon, “Combinatory Analysis,” Cambridge Univ. Press, London/New York, 1916; reprinted by Chelsea, New York, 1960.

[6] 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.

[7] Franzblau, D. S. and Zeilberger, D. (1982). A bijective proof of the hook-length formula. J. Algorithms 3, 317–343.

[8] Pak, I. M. and Stoyanovskii, A. V. (1992). A bijective proof of the hook-length formula. Funct. Anal. Appl. 24.

[9] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]