フック長の公式

数学の組合せ論において、フック長の公式（フックちょうのこうしき、）とは、与えられたヤング図形の形をした標準盤を数える公式である。表現論や、確率論、アルゴリズム解析などの多種多様な分野に応用があり、などが例としてあげられる。
 Definitions and statement 
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 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  or  and . The hook-length  is the number of cells in the hook .

Then the hook-length formula expresses the number of standard Young tableaux of shape , sometimes denoted by , as



where the product is over all cells  of .

 Example 
右|サムネイル|A tableau listing the hook length of each cell in the Young diagram 
The figure on the right shows hook-lengths for all cells in the Young diagram  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. 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. This earlier formula was deduced independently by G. Frobenius and A. Young in 1900 and 1902 respectively using algebraic methods. 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 found an alternate proof for the Young–Frobenius formula in 1916 using difference methods. P. A. MacMahon. “Combinatory Analysis,” Cambridge Univ. Press, London/New York, 1916; reprinted by Chelsea, New York, 1960.

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. Knuth, Donald (1973). The Art of Computer Programming, Volume 3: Sorting and Searching, 3rd Edition, Addison–Wesley, p. 63 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. A. P. Hillman and R. M. Grassl. Reverse plane partitions and tableau hook numbers, J. Comb. Theory, Ser. A 21 (1976), 216–221. 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. 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. J. B. Remmel adapted the original Frame–Robinson–Thrall proof into the first bijective proof for the hook-length formula in 1982. J. B. Remmel. Bijective proofs of formulae for the number of standard Young tableaux, Linear and Multilinear Algebra 11 (1982), 45–100. A direct bijective proof was first discovered by D. S. Franzblau and D. Zeilberger in 1982. Franzblau, D. S. and Zeilberger, D. (1982). A bijective proof of the hook-length formula. J. Algorithms 3, 317–343. D. Zeilberger also converted the Greene–Nijenhuis–Wilf hook walk proof into a bijective proof in 1984. D. Zeilberger. A short hook-lengths bijection inspired by the Greene–Nijenhuis–Wilf proof, Discrete Math. 51 (1984), 101–108. 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. 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.

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. R. M. Thrall. A combinatorial problem, Michigan Math. J. 1 (1952), 81–88. B. E. Sagan gave a shifted hook walk proof for the hook-length formula for shifted Young tableaux in 1980. Sagan, B. On selecting a random shifted Young tableau. J. Algorithms 1, 3 (1980), 213–234. B. E. Sagan and Y. N. Yeh proved the hook-length formula for binary trees using the hook walk in 1989. Sagan, B. E., and Yeh, Y. N. Probabilistic algorithms for trees. Fibonacci Quart. 27, 3 (1989), 201–208.

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

 フックウォークを用いた確率論的証明法 
これは1979年に、  C. Greene, A. Nijenhuis と H. S. Wilf によって発見された、確率論的証明法である。証明の概略は、次のとおりである。



を定義し、 を証明する。 

は以下で与えられる。



ここで、  は、がヤング図形λから一つのコーナーセルを削除することで得られるヤングタブローであることを表している。

そのようなμの全体にわたって和をとる。ここで、慣習として を空のダイアグラムとして、 を用いる。

上の式に対する説明は、「ヤングタブローの最大項はそのコーナーセルで生じるものである」となる。

そのセルを削除することで、μの形のヤングタブローを得る。

μの形のヤングタブローの数が  であり、それらμに関して和をとることでその式を得る。
右|サムネイル|Corners of the Young diagram (5,3,2,1,1)
ここで、であることにも注意されたい。それゆえ、次を示せば十分で、



その結果、  は帰納的に証明される。

上の式の和は、次のように式を書き換えることによって、確率の和と捉えることができる。



われわれはこのようにして、 が、ヤング図形μの集合上の確率測度を定めている。（ここで ）

これはフックウォークと呼ばれるランダムウォークを定義を用いた構成法によるものである。

フックウォークは、ヤング図形λの上で、ひとつのコーナーセルを選択する。

フックウォークは次のルールによって定義される。

(1)   個のセルのなかから一様ランダムにひとつのセルを選び、そこからランダムウォークを始める。

(2) 現在の セルの次のセルは、一様ランダムにフック から選ぶ。

(3) 一つのコーナーに到達するまでこれを続け、そのコーナーセルをとする。

命題: λに属するすべてのコーナーセル に対して、次が成り立つ。



ここで、 .

この命題を得れば、すべての  に関して和をとることによって、 を得る。

 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 ,  or .

 Detailed discussion 
The complex irreducible representations  of the symmetric group are indexed by partitions  of  (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 inner product with  is , because . Note that  is equal to . Hence



An immediate consequence of this is



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

The computation also shows that:



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 
By the above considerations



So that



where  is the Vandermonde determinant.

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 .

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.W. Fulton, J. Harris. Representation Theory: A First Course Springer-Verlag , New York, 1991 All that remains is tracking that coefficient with a mixture of cleverness and brute force: Multiplying



and



we conclude that the coefficient that we are looking for is



which can be written as



The latter sum is equal to the following determinant



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



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 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 and independently Benjamin F. Logan and Lawrence A. Shepp B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Advances in Math. 26 (1977), no. 2, 206–222. 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.  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.  If  is a partition of some integer , a reverse plane partition of  with shape  is obtained by filling in the boxes in the Young diagram with non-negative integers such that the entries add to  and are non-decreasing along each row and down each column.  The hook lengths  can be defined as with Young tableau.  If  denotes the number of reverse plane partitions of  with shape , then the generating function can be written as



Stanley discovered another formula for the same generating function.R.P. Stanley, "Ordered Structures and Partitions" PhD Thesis, Harvard University, 1971 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 natural labelings of .

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

 .

So a natural labeling is simply a standard Young tableau, i.e. 

 Yet another proof of the hook length formula 
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



Finally, applying L'Hopital's rule  times yields the hook length formula



 Specialization of Schur functions 
Specializing the schur functions to the variables  there is the formula



The number  is defined as



where  is the conjugate partition

 Skew shape formula 
There is a generalization of this formula for skew shapes, Morales, A. H., Pak, I., and Panova, G. Hook formulas for skew shapes, arXiv:1512.08348.



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



 脚注 

 関連項目 

 ヤング図形
 シューア多項式

 外部リンク 

 A published book on longest increasing subsequences by Dan Romik (PDF copy available for download). Contains discussions of the hook length formula and several of its variants, with applications to the mathematics of longest increasing subsequences.

Category:組合せ論
Category:数学に関する記事