In combinatorial mathematics, the hook length formula is a formula for the number of standard Young tableaux whose shape is a given Young diagram. 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.

Definitions and statement

edit

Let   be a partition of  . It is customary to interpret   graphically as a Young diagram, namely a left-justified array of square cells with   rows of lengths  . A (standard) Young tableau of shape   is a filling of the   cells of the Young diagram with all the integers  , with no repetition, such that each row and each column form increasing sequences. For the cell in position  , in the  th row and  th column, the hook   is the set of cells   such that   and   or   and  . The hook length   is the number of cells in  .

The hook length formula expresses the number of standard Young tableaux of shape  , denoted by   or  , as

 

where the product is over all cells   of the Young diagram.

Examples

edit
 
A tableau listing the hook length of each cell in the Young diagram
 

The figure on the right shows hook lengths for the cells in the Young diagram  , corresponding to the partition 9 = 4 + 3 + 1 + 1. The hook length formula gives the number of standard Young tableaux as:

 

A Catalan number  counts Dyck paths with   steps going up (U) interspersed with   steps going down (D), such that at each step there are never more preceding D's than U's. These are in bijection with the Young tableaux of shape  : a Dyck path corresponds to the tableau whose first row lists the positions of the U-steps, while the second row lists the positions of the D-steps. For example, UUDDUD correspond to the tableaux with rows 125 and 346.

This shows that  , so the hook formula specializes to the well-known product formula

 

History

edit

There are other formulas for  , but the hook length formula is particularly simple and elegant. A less convenient formula expressing   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.[3]

The hook length formula itself was discovered in 1953 by Frame, Robinson, and Thrall as an improvement to the Young–Frobenius formula. Sagan[4] describes the discovery as follows.

One Thursday in May of 1953, Robinson was visiting Frame at Michigan State University. 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. This surprised Thrall, who was in the audience, because he had just proved the same result on the same day!

Despite the simplicity of the hook length formula, the Frame–Robinson–Thrall proof is not very insightful and does not provide any intuition for the role of the hooks. 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.[6] Greene, Nijenhuis, and Wilf found a probabilistic proof using the hook walk in which the hook lengths appear naturally in 1979.[7] 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 Franzblau and Zeilberger in 1982.[9] Zeilberger also converted the Greene–Nijenhuis–Wilf hook walk proof into a bijective proof in 1984.[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.[11][12][4]

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] Sagan gave a shifted hook walk proof for the hook length formula for shifted Young tableaux in 1980.[14] Sagan and Yeh proved the hook length formula for binary trees using the hook walk in 1989.[15] Proctor gave a poset generalization (see below).

Probabilistic proof

edit

Knuth's heuristic argument

edit

The hook length formula can be understood intuitively using the following heuristic, but incorrect, argument suggested by D. E. Knuth.[16] Given that each element of a tableau is the smallest in its hook and filling the tableau shape at random, the probability that cell   will contain the minimum element of the corresponding hook is the reciprocal of the hook length. Multiplying these probabilities over all   and   gives the formula. This argument is fallacious since the events are not independent.

Knuth's argument is however correct for the enumeration of labellings on trees satisfying monotonicity properties analogous to those of a Young tableau. In this case, the 'hook' events in question are in fact independent events.

Probabilistic proof using the hook walk

edit

This is a probabilistic proof found by C. Greene, A. Nijenhuis, and H. S. Wilf in 1979.[7] Define

 

We wish to show that  . First,

 
 
Corners of the Young diagram (5,3,2,1,1)

where the sum runs over all Young diagrams   obtained from   by deleting one corner cell. (The maximal entry of the Young tableau of shape   occurs at one of its corner cells, so deleting it gives a Young tableaux of shape  .)

We define  and  , so it is enough to show the same recurrence

 

which would imply   by induction. The above sum can be viewed as a sum of probabilities by writing it as

 

We therefore need to show that the numbers   define a probability measure on the set of Young diagrams   with  . This is done in a constructive way by defining a random walk, called the hook walk, on the cells of the Young diagram  , which eventually selects one of the corner cells of   (which are in bijection with diagrams   for which  ). The hook walk is defined by the following rules.

  1. Pick a cell uniformly at random from   cells. Start the random walk from there.
  2. Successor of current cell   is chosen uniformly at random from the hook  .
  3. Continue until you reach a corner cell  .

Proposition: For a given corner cell   of  , we have

 

where  .

Given this, summing over all corner cells   gives   as claimed.

Connection to representations of the symmetric group

edit

The hook length formula is of great importance in the representation theory of the symmetric group  , where the number   is known to be equal to the dimension of the complex irreducible representation   associated to  .

Detailed discussion

edit

The complex irreducible representations   of the symmetric group are indexed by partitions   of   (see Specht module) . Their characters are related to the theory of symmetric functions via the Hall inner product:

 

where   is the Schur function associated to   and   is the power-sum symmetric function of the partition   associated to the cycle decomposition of  . For example, if   then  .

Since the identity permutation   has the form   in cycle notation,  , the formula says

 

The expansion of Schur functions in terms of monomial symmetric functions uses the Kostka numbers:

 

Then the inner product with   is  , because  . Note that   is equal to  , so that   from considering the regular representation of  , or combinatorially from the Robinson–Schensted–Knuth correspondence.

The computation also shows that:

 

This is the expansion of   in terms of Schur functions using the coefficients given by the inner product, since  . 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   by irreducible   modules, and taking characters. See Schur–Weyl duality.

Proof of hook formula using Frobenius formula

edit

Source:[17]

By the above considerations

 

so that

 

where   is the Vandermonde determinant.

For the partition  , define   for  . For the following we need at least as many variables as rows in the partition, so from now on we work with   variables  .

Each term   is equal to

 

(See Schur function.) Since the vector   is different for each partition, this means that the coefficient of   in  , denoted  , is equal to  . This is known as the Frobenius Character Formula, which gives one of the earliest proofs.[17]

It remains only to simplify this coefficient. Multiplying

 

and

 

we conclude that our coefficient as

 

which can be written as

 

The latter sum is equal to the following determinant

 

which column-reduces to a Vandermonde determinant, and we obtain the formula

 

Note that   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  : one shows  , where the latter product runs over the  th row of the Young diagram.

Connection to longest increasing subsequences

edit

The hook length formula also has important applications to the analysis of longest increasing subsequences in random permutations. If   denotes a uniformly random permutation of order  ,   denotes the maximal length of an increasing subsequence of  , and   denotes the expected (average) value of  , Anatoly Vershik and Sergei Kerov[18] and independently Benjamin F. Logan and Lawrence A. Shepp[19] showed that when   is large,   is approximately equal to  . This answers a question originally posed by Stanislaw Ulam. 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. Since the definition of Plancherel measure involves the quantity  , 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. Their analysis again makes crucial use of the fact that   has a number of good formulas, although instead of the hook length formula it made use of one of the determinantal expressions.

edit

The formula for the number of Young tableaux of shape   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. The hook lengths   can be defined as with Young tableaux. If πn denotes the number of reverse plane partitions of n with shape λ, then the generating function can be written as

 

Stanley discovered another formula for the same generating function.[22] In general, if   is any poset with   elements, the generating function for reverse  -partitions is

 

where   is a polynomial such that   is the number of linear extensions of  .

In the case of a partition  , we are considering the poset in its cells given by the relation

 .

So a linear extension is simply a standard Young tableau, i.e.  

Proof of hook formula using Stanley's formula

edit

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  

 

It would be violent to plug in 1, but the right hand side is a continuous function inside the unit disk and a polynomial is continuous everywhere so at least we can say

 

Applying L'Hôpital's rule   times yields the hook length formula

 

Semi-standard tableaux hook length formula

edit

The Schur polynomial   is the generating function of semistandard Young tableaux with shape   and entries in  . Specializing this to   gives the number of semi-standard tableaux, which can be written in terms of hook lengths:

 

The Young diagram   corresponds to an irreducible representation of the special linear group  , and the Schur polynomial is also the character of the diagonal matrix   acting on this representation. The above specialization is thus the dimension of the irreducible representation, and the formula is an alternative to the more general Weyl dimension formula.

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

 

where   for the conjugate partition  .

Skew shape formula

edit

There is a generalization of this formula for skew shapes, [23]

 

where the sum is taken over excited diagrams of shape   and boxes distributed according to  .

A variation on the same theme is given by Okounkov and Olshanski[24] of the form

 

where   is the so-called shifted Schur function  .

Generalization to d-complete posets

edit

Young diagrams can be considered as finite order ideals in the poset  , and standard Young tableaux are their linear extensions. Robert Proctor has given a generalization of the hook length formula to count linear extensions of a larger class of posets generalizing both trees and skew diagrams.[25][26]

References

edit
  1. ^ G. Frobenius. Uber die charaktere der symmetrischer gruppe, Preuss. &ad. Wk. sitz. (1900), 516–534.
  2. ^ A. Young. Quantitative substitutional analysis II, Proc. London Math. Sot., Ser. 1, 35 (1902), 361–397.
  3. ^ P. A. MacMahon. “Combinatory Analysis,” Cambridge Univ. Press, London/New York, 1916; reprinted by Chelsea, New York, 1960.
  4. ^ a b Sagan, Bruce (2001). The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Functions, 2nd edition. Springer-Verlag. ISBN 0-387-95067-2.
  5. ^ Knuth, Donald (1973). The Art of Computer Programming, Volume 3: Sorting and Searching, 3rd Edition, Addison–Wesley, p. 63
  6. ^ Hillman, A. P.; Grassl, R. M. (1976). "Reverse plane partitions and tableau hook numbers". Journal of Combinatorial Theory. Series A. 21 (2): 216–221. doi:10.1016/0097-3165(76)90065-0.
  7. ^ a b Greene, Curtis; Nijenhuis, Albert; Wilf, Herbert S. (1979). "A probabilistic proof of a formula for the number of Young tableaux of a given shape". Advances in Mathematics. 31 (1): 104–109. doi:10.1016/0001-8708(79)90023-9.
  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. ^ Zeilberger, Doron (1984). "A short hook-lengths bijection inspired by the Greene–Nijenhuis–Wilf proof". Discrete Mathematics. 51 (1): 101–108. doi:10.1016/0012-365X(84)90027-X.
  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.
  16. ^ Knuth, Donald (1973), The Art of Computer Programming, Volume 3: Sorting and Searching, 3rd Edition, Addison–Wesley, p. 63, ISBN 0-201-03803-X.
  17. ^ a b Fulton, William, 1939- (1991). Representation theory : a first course. Harris, Joe, 1951-. New York: Springer-Verlag. pp. 49–50. ISBN 0387974954. OCLC 22861245.{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
  18. ^ Vershik, A. M.; Kerov, C. V. (1977), "Asymptotics of the Plancheral measure of the symmetric group and a limiting form for Young tableaux", Dokl. Akad. Nauk SSSR 233: 1024–1027
  19. ^ Logan, B. F.; Shepp, L. A. (1977). "A variational problem for random Young tableaux". Advances in Mathematics. 26 (2): 206–222. doi:10.1016/0001-8708(77)90030-5.
  20. ^ Knuth, Donald (1973), The Art of Computer Programming, vol. 3 (1 ed.), Addison–Wesley, pp. 61–62
  21. ^ Stanley, Richard P. (1971), "Theory and applications of plane partitions, 2", Studies in Applied Mathematics, 50: 259–279, doi:10.1002/sapm1971503259
  22. ^ R.P. Stanley, "Ordered Structures and Partitions" PhD Thesis, Harvard University, 1971
  23. ^ Morales, Alejandro H.; Pak, Igor; Panova, Greta (2018). "Hook formulas for skew shapes I. q-analogues and bijections". Journal of Combinatorial Theory. Series A. 154: 350–405. arXiv:1512.08348. doi:10.1016/j.jcta.2017.09.002.
  24. ^ Okounkov, A. and Olshanski, G. Shifted Schur functions, Algebra I Analiz, 9.2 (1997), 73-146.
  25. ^ Proctor, Robert (1999). "Dynkin diagram classification of λ-minuscule Bruhat lattices and of d-complete posets". Journal of Algebraic Combinatorics. 9: 61–94. doi:10.1023/A:1018615115006.
  26. ^ Kim, Jang Soo; Yoo, Meesue (2019). "Hook length property of d-complete posets via q-integrals". Journal of Combinatorial Theory. Series A. 162: 167–221. arXiv:1708.09109. doi:10.1016/j.jcta.2018.11.003. S2CID 57759574.
edit