Jump to content

User:TestFunction/sandbox

From Wikipedia, the free encyclopedia
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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 in diverse areas such as probability, algebraic geometry, group theory, representation theory, and algorithm analysis; for example, 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 i=1,2,…,m and j=1,2,…,λ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 |Hλ(i,j)|, the number of cells in the hook Hλ(i,j).

Then the hook-length formula is

There are other formulas for dλ, but the hook-length formula is particularly simple. In fact, 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 formula for dλ in terms of a determinant. [1] This earlier formula was deduced independently by G. Frobenius and A. Young in 1900 and 1902 respectively using algebraic methods. [2] [3] P. A. MacMahon found an alternate proof for the Young-Frobenius formula in 1916 using difference methods. [4]

Despite the simplicity of the hook-length formula, the Frame-Robinson-Thrall proof is highly non-trivial and does not provide an intuitive argument as to why hooks appear in the formula. The search for a short, intuitive explanation befitting such a simple result gave rise to many alternate proofs for the hook-length formula. [5] A. P. Hillman and R. M. 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. [6] C. Greene, A. Nijenhuis, and H. S. Wilf found a probabilistic proof using the hook walk in which the hook lengths appear naturally in 1979. [7] J. B. Remmel adapted the original Frame-Robinson-Thrall proof into the first bijective proof for the hook-length formula in 1982. [8] A direct bijective proof was first discovered by D. S. Franzblau and D. Zeilberger in 1982. [9] D. Zeilberger also converted the Greene-Nijenhuis-Wilf hook walk proof into a bijective proof in 1984. [10] A simpler direct 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. [11] [12]

Meanwhile, the hook-length formula has been generalized in several ways. R. M. Thrall found the analogue to the hook-length formula for shifted Young Tableaux in 1952. [13] B. E. Sagan gave a shifted hook walk proof for the hook-length formula for shifted Young tableaux in 1980. [14] B. E. Sagan and Y. N. Yeh proved the hook-length formula for binary trees using the hook walk in 1989. [15]


References

  1. ^ 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.
  2. ^ G. Frobenius. Uber die charaktere der symmetrischer gruppe, Preuss. &ad. Wk. sitz. (1900), 516-534.
  3. ^ A. Young. Quantitative substitutional analysis II, Proc. London Math. Sot., Ser. 1, 35 (1902), 361-397.
  4. ^ P. A. MacMahon. “Combinatory Analysis,” Cambridge Univ. Press, London/New York, 1916; reprinted by Chelsea, New York, 1960.
  5. ^ Knuth, Donald (1973). The Art of Computer Programming, Volume 3: Sorting and Searching, 3rd Edition, Addison-Wesley, p. 63
  6. ^ A. P. Hillman and R. M. Grassl. Reverse plane partitions and tableau hook numbers, J. Comb. Theory, Ser. A 21 (1976), 216–221.
  7. ^ 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.
  8. ^ J. B. Remmel. Bijective proofs of formulae for the number of standard Young tableaux, Linear and Multilinear Algebra 11 (1982), 45–100.
  9. ^ Franzblau, D. S. and Zeilberger, D. (1982). A bijective proof of the hook-length formula. J. Algorithms 3, 317–343.
  10. ^ D. Zeilberger. A short hook-lengths bijection inspired by the Greene–Nijenhuis–Wilf proof, Discrete Math. 51 (1984), 101–108.
  11. ^ Pak, I. M. and Stoyanovskii, A. V. (1992). A bijective proof of the hook-length formula. Funct. Anal. Appl. 24.
  12. ^ 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.
  13. ^ R. M. Thrall. A combinatorial problem, Michigan Math. J. 1 (1952), 81–88.
  14. ^ Sagan, B. On selecting a random shifted Young tableau. J. Algorithms 1, 3 (1980), 213–234.
  15. ^ Sagan, B. E., and Yeh, Y. N. Probabilistic algorithms for trees. Fibonacci Quart. 27, 3 (1989), 201–208.


Despite the simplicity of the hook-length formula, initially it was not even clear why hooks appeared in the formula. Thus there were many attempts to find a simpler proof, resulting in many alternate, more intuitive proofs. was an urge to develop

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. ))

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).



copy


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. [1] D. S. Franzblau and D. Zeilberger converted this proof into the first direct bijective proof in 1982. A direct bijective proof was first discovered by D. S. Franzblau and D. Zeilberger in 1982. [2] Meanwhile, Remmel adapted the original Young-Frobenius proof and Frame-Robinson-Thrall proof into the first bijective proof in 1982. 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. [3] [4]

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.


In fact, the hook-length formula was discovered in 1954 by J. S. Frame, G. de B. Robinson, and R. M. Thrall in a successful attempt to improve a less convenient formula for dλ in terms of a determinant.

In fact, the hook-length formula was discovered in 1954 by J. S. Frame, G. de B. Robinson, and R. M. Thrall as an attempt to improve a less convenient determinant formula for dλ.


Thus there were many attempts to find a simpler proof, resulting in many alternate, more intuitive proofs. was an urge to develop


it was not intuitively clear from the 1954 proof why hooks appeared in the formula.

Many alternate proofs for the hook-length formula have been developed, in particular because no short, intuitive explanation befitting such a simple result had been found. Indeed, despite the simplicity of the hook-length formula, initially it was not even clear why hooks appeared in the formula.


[5] [6]


A. P. Hillman and R. M. Grassl gave the first (correct) 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.

J. B. Remmel adapted the original Frame-Robinson-Thrall proof based on the Young-Frobenius proof for the determinant formula into the first bijective proof for the hook-length formula in 1982.

knuth said there should be simple proof ... but unfortunately his own simple proof was flawed


Despite the simplicity of the hook-length formula, the Frame-Robinson-Thrall proof is highly non-trivial and does not provide an intuitive argument as to why hooks appear in the formula. The search for a short, intuitive explanation befitting such a simple result gave rise to many alternate proofs for the hook-length formula. [7] A. P. Hillman and R. M. 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. [8] Inspired by this result, C. Greene, A. Nijenhuis, and H. S. Wilf found a probabilistic proof (using the hook walk) in which the hook lengths appear naturally in 1979. [9] Remmel adapted the original Frame-Robinson-Thrall proof based on the Young-Frobenius proof into the first bijective proof in 1982. A direct bijective proof was first discovered by D. S. Franzblau and D. Zeilberger in 1982. [10] Meanwhile, D. Zeilberger converted the Greene-Nijenhuis-Wilf proof into a bijective proof in 1984. A simpler direct 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. [11] [12]

  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. ^ Franzblau, D. S. and Zeilberger, D. (1982). A bijective proof of the hook-length formula. J. Algorithms 3, 317–343.
  3. ^ Pak, I. M. and Stoyanovskii, A. V. (1992). A bijective proof of the hook-length formula. Funct. Anal. Appl. 24.
  4. ^ 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.
  5. ^ R. P. Stanley. Enumerative Combinatorics, Vol. 1, 2, Cambridge University Press, 1997, 1999.
  6. ^ C. Krattenthaler. An involution principle-free bijective proof of Stanley’s hook-content formula, Discrete Math. Theor. Comput. Sci. 3 (1998/99), no. 1, 11–32.
  7. ^ Knuth, Donald (1973). The Art of Computer Programming, Volume 3: Sorting and Searching, 3rd Edition, Addison-Wesley, p. 63
  8. ^ A. P. Hillman and R. M. Grassl. Reverse plane partitions and tableau hook numbers, J. Comb. Theory, Ser. A 21 (1976), 216–221.
  9. ^ 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.
  10. ^ Franzblau, D. S. and Zeilberger, D. (1982). A bijective proof of the hook-length formula. J. Algorithms 3, 317–343.
  11. ^ Pak, I. M. and Stoyanovskii, A. V. (1992). A bijective proof of the hook-length formula. Funct. Anal. Appl. 24.
  12. ^ 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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=User:TestFunction/sandbox&oldid=585573702"