“Hook length formula”的意思、由来-开放百科全书

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.

Definitions and statement

It is customary to interpret

graphically as a Young diagram, namely a left-justified array of square cells with

rows and

cells in the

th row for each

A standard Young tableau of shape

is a Young diagram of shape

in which each of the

cells contains a distinct integer between 1 and

(i.e., no repetition), such that each row and each column form increasing sequences.

For each cell of the Young diagram in coordinates

(that is, the cell in the

th row and

th column), the hook

is the set of cells

such that

and

Then the hook-length formula expresses the number of standard Young tableaux of shape

, sometimes denoted by

, as

Example

The figure on the right shows hook-lengths for all cells in the Young diagram {{math|λ}} of the partition
9 = 4 + 3 + 1 + 1. Then the number of standard Young tableaux

for this Young diagram can be computed as

History

There are other formulas for

, but the hook-length formula is particularly simple and elegant.

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 expressing

in terms of a determinant.

This earlier formula 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.

Despite the simplicity of the hook-length formula, the Frame–Robinson–Thrall proof is uninsightful 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.

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.

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.

J. B. Remmel adapted the original Frame–Robinson–Thrall proof into the first bijective proof for the hook-length formula in 1982.

A direct bijective proof was first discovered by D. S. Franzblau and D. Zeilberger in 1982.

D. Zeilberger also converted the Greene–Nijenhuis–Wilf hook walk 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.

R. M. Thrall found the analogue to the hook-length formula for shifted Young Tableaux in 1952.

B. E. Sagan gave a shifted hook walk proof for the hook-length formula for shifted Young tableaux in 1980.

B. E. Sagan and Y. N. Yeh proved the hook-length formula for binary trees using the hook walk in 1989.

Proofs

Knuth's heuristic argument

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

This is a probabilistic proof found by C. Greene, A. Nijenhuis, and H. S. Wilf in 1979.^[17] Here is a sketch of the proof. Define

where

denotes that

are Young tableau obtained from

by deleting one corner cell from

. The sum is taken over all such

. Here we are taking the convention that

, where

denotes the empty diagram. The explanation for the above equation is that the maximal entry of the Young tableau of shape

occurs at one of its corner cells. By deleting that cell we will obtain a Young tableau of shape

. Since the number of Young tableau of shape

, taking the sum over all such

we get the equation.

and the result

then follows by induction. The above sum can also be viewed as a sum of probabilities by rewriting the equation to be shown as

We therefore need to show that the numbers

define a probability measure on the set of Young diagrams

(where

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

Once we have the above proposition, taking the sum over all possible corner cells

we have

, as claimed.

Connection to representation theory

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

, and is frequently denoted by

Detailed discussion

The complex irreducible representations

of the symmetric group are indexed by partitions

(for an explicit construction see Specht module) . Their characters are related to the theory of symmetric functions via the Hall inner product in the following formula

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,

. Then the formula says

Considering the expansion of Schur functions in terms of monomial symmetric functions using the Kostka numbers

The above equality is also a simple consequence of the Robinson–Schensted–Knuth correspondence.

Which is the expansion of

in terms of Schur functions using the coefficients given by the inner product, because

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.

Outline of the proof of the hook formula using Frobenius formula

For a given 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

See Schur function. Since the vector

is different for each partition, this means that the coefficient of

, denoted

, is equal to

. This is known as the Frobenius Character Formula, which gives one of the earliest proofs.^[18]

All that remains is tracking that coefficient with a mixture of cleverness and brute force: Multiplying

Note that

is the hook length of the first box in each row of the Young Diagram. Transforming this expression into the form

claimed by the hook-length formula is a fairly simple exercise in combinatorics: For any given

, one has to argue that

, where the latter product ranges over all cells

in the

-row of the Young diagram of

Connection to longest increasing subsequences

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 ^[19] and independently Benjamin F. Logan and Lawrence A. Shepp ^[20] 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.

Related formulas

The formula for the number of Young tableau of a given shape was originally derived from the Frobenius determinant formula in connection to representation theory.^[21] If the shape of a Young diagram is given by the row lengths

, then the number of tableau with that shape is given by

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.^[22] If {{mvar|λ}} is a partition of some integer {{mvar|p}}, a reverse plane partition of {{mvar|n}} with shape {{mvar|λ}} is obtained by filling in the boxes in the Young diagram with non-negative integers such that the entries add to {{mvar|n}} and are non-decreasing along each row and down each column. The hook lengths

can be defined as with Young tableau. If {{math|π_n}} denotes the number of reverse plane partitions of {{mvar|n}} with shape {{mvar|λ}}, then the generating function can be written as

Stanley discovered another formula for the same generating function.^[23] In general, if

is any poset with

elements, the generating function for reverse

-partitions is

In the case of a partition

, we are considering the poset in its cells given by the relation

Yet another proof of the hook length formula

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

Specialization of Schur functions

Skew shape formula

where the sum is taken over excited diagrams of shape

and boxes distributed according to

A formula for the Catalan numbers

The Catalan numbers are ubiquitous in enumerative combinatorics. Not surprisingly, they are also part of this story:

Lets briefly mention why. When doing a Dyck path we may go up (U) or down (D). So for any Dyck path of length

consider the tableaux of shape

such that the first row is given by the numbers

such that the

-th step was up and in the second row given by the positions in which it goes down. For example, UUDDUD correspond to the tableaux with rows 125 and 346.

The hook formula gives another way of getting a closed formula for the Catalan numbers

See also

References

1. ^Frame, J. S., Robinson, G. de B. and Thrall, R. M. (1954). The hook graphs of the symmetric group.Can. 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 numberof 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 andMultilinear Algebra 11 (1982), 45–100.
9. ^Franzblau, D. S. and Zeilberger, D. (1982). A bijective proof of the hook-length formula. J. Algorithms3, 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.
16. ^{{citation|title=The Art of Computer Programming, Volume 3: Sorting and Searching, 3rd Edition|first=Donald|last=Knuth|publisher=Addison–Wesley|year=1973|isbn=0-201-03803-X|page=63}}.
17. ^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.
18. ^W. Fulton, J. Harris. Representation Theory: A First Course Springer-Verlag, New York, 1991
19. ^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
20. ^B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Advances in Math. 26 (1977), no. 2, 206–222.
21. ^{{citation|last1 = Knuth| first1 = Donald|publisher = Addison–Wesley|year= 1973|authorlink=Donald Ervin Knuth|edition=1|title = The Art of Computer Programming|volume=3|pages=61–62}}
22. ^{{Citation | authorlink=Richard P. Stanley | last1=Stanley | first1=Richard P. | title=Theory and applications of plane partitions, 2 | year=1971 | journal=Studies in Applied Mathematics | volume=50 | pages=259–279}}
23. ^R.P. Stanley, "Ordered Structures and Partitions" PhD Thesis, Harvard University, 1971
24. ^Morales, A. H., Pak, I., and Panova, G.Hook formulas for skew shapes,arXiv:1512.08348.