フック長の公式

数学の組合せ論において、フック長の公式（フックちょうのこうしき、）とは、与えられたヤング図形の形をした標準盤を数える公式である。表現論や、確率論、アルゴリズム解析などの多種多様な分野に応用があり、などが例としてあげられる。
Definitions and statement.
Let formula_1 be a partition of formula_2. It is customary to interpret formula_3 graphically as a Young diagram, namely a left-justified array of square cells with formula_4 rows and formula_5 cells in the formula_6th row for each formula_7. A standard Young tableau of shape formula_3 is a Young diagram of shape formula_3 in which each of the formula_2 cells contains a distinct integer between 1 and formula_2 (i.e., no repetition), such that each row and each column form increasing sequences. For each cell of the Young diagram in coordinates formula_12 (that is, the cell in the formula_6th row and formula_14th column), the hook formula_15 is the set of cells formula_16 such that formula_17 and formula_18 or formula_19 and formula_20. The hook-length formula_21 is the number of cells in the hook formula_15.
Then the hook-length formula expresses the number of standard Young tableaux of shape formula_3, sometimes denoted by formula_24, as
where the product is over all cells formula_12 of formula_3.
Example.
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 formula_24 for this Young diagram can be computed as
History.
There are other formulas for formula_24, 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 formula_24 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. 
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. 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. Given that each element of a tableau is the smallest in its hook and filling the tableau shape at random, the probability that cell formula_12 will contain the minimum element of the corresponding hook is the reciprocal of the hook length. Multiplying these probabilities over all formula_6 and formula_14 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 によって発見された、確率論的証明法である。証明の概略は、次のとおりである。
を定義し、 formula_36を証明する。 
formula_24は以下で与えられる。
ここで、 formula_39 は、formula_40がヤング図形λから一つのコーナーセルを削除することで得られるヤングタブローであることを表している。
そのようなμの全体にわたって和をとる。ここで、慣習として formula_41を空のダイアグラムとして、 formula_42を用いる。
上の式に対する説明は、「ヤングタブローの最大項はそのコーナーセルで生じるものである」となる。
そのセルを削除することで、μの形のヤングタブローを得る。
μの形のヤングタブローの数が formula_43であり、それらμに関して和をとることでその式を得る。
ここで、formula_44であることにも注意されたい。それゆえ、次を示せば十分で、
その結果、 formula_46 は帰納的に証明される。
上の式の和は、次のように式を書き換えることによって、確率の和と捉えることができる。
われわれはこのようにして、 formula_48が、ヤング図形μの集合上の確率測度を定めている。（ここで formula_39）
これはフックウォークと呼ばれるランダムウォークを定義を用いた構成法によるものである。
フックウォークは、ヤング図形λの上で、ひとつのコーナーセルを選択する。
フックウォークは次のルールによって定義される。
(1) formula_50 個のセルのなかから一様ランダムにひとつのセルを選び、そこからランダムウォークを始める。
(2) 現在の formula_12セルの次のセルは、一様ランダムにフック formula_52から選ぶ。
(3) 一つのコーナーに到達するまでこれを続け、そのコーナーセルをformula_53とする。
命題: λに属するすべてのコーナーセル formula_16に対して、次が成り立つ。
ここで、 formula_56.
この命題を得れば、すべての formula_57 に関して和をとることによって、 formula_58を得る。
Connection to representation theory.
The hook-length formula is of great importance in the representation theory of the symmetric group formula_59, where the number formula_24 is known to be equal to the dimension of the complex irreducible representation formula_61 associated to formula_3, and is frequently denoted by formula_63, formula_64 or formula_65.
Detailed discussion.
The complex irreducible representations formula_66 of the symmetric group are indexed by partitions formula_67 of formula_68 (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 formula_70 is the Schur function associated to formula_67 and formula_72 is the power-sum symmetric function of the partition formula_73 associated to the cycle decomposition of formula_74. For example, if formula_75 then formula_76.
Since the identity permutation formula_77 has the form formula_78 in cycle notation, formula_79. Then the formula says
Considering the expansion of Schur functions in terms of monomial symmetric functions using the Kostka numbers
the inner product with formula_82 is formula_83, because formula_84. Note that formula_85 is equal to formula_86. 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 formula_90 in terms of Schur functions using the coefficients given by the inner product, because formula_91. 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 formula_92 by irreducible formula_93 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 formula_96 is the Vandermonde determinant.
For a given partition formula_97 define formula_98 for formula_99. For the following we need at least as many variables as rows in the partition, so from now on we work with formula_100 variables formula_101.
Each term formula_102 is equal to
See Schur function. Since the vector formula_104 is different for each partition, this means that the coefficient of formula_105 in formula_106, denoted formula_107, is equal to formula_108. This is known as the Frobenius Character Formula, which gives one of the earliest proofs. 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 formula_115 is the hook length of the first box in each row of the Young Diagram. Transforming this expression into the form formula_116 claimed by the hook-length formula is a fairly simple exercise in combinatorics: For any given formula_117, one has to argue that formula_118, where the latter product ranges over all cells formula_119 in the formula_6-row of the Young diagram of formula_3.
Connection to longest increasing subsequences.
The hook length formula also has important applications to the analysis of longest increasing subsequences in random permutations. If formula_122 denotes a uniformly random permutation of order formula_2, formula_124 denotes the maximal length of an increasing subsequence of formula_122, and formula_126 denotes the expected (average) value of formula_124, Anatoly Vershik and Sergei Kerov and independently Benjamin F. Logan and Lawrence A. Shepp showed that when formula_2 is large, formula_126 is approximately equal to formula_130. 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 formula_24, 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 formula_24 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 formula_133, 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 formula_135 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. In general, if formula_137 is any poset with formula_68 elements, the generating function for reverse formula_137-partitions is
where formula_141 is a polynomial such that formula_142 is the number of natural labelings of formula_137.
In the case of a partition formula_67, we are considering the poset in its cells given by the relation
So a natural labeling is simply a standard Young tableau, i.e. formula_146
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 formula_148
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 formula_68 times yields the hook length formula
Specialization of Schur functions.
Specializing the schur functions to the variables formula_153 there is the formula
The number formula_155 is defined as
where formula_157 is the conjugate partition
Skew shape formula.
There is a generalization of this formula for skew shapes, 
where the sum is taken over "excited diagrams" of shape formula_3 and boxes distributed according to formula_40.
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 formula_68 consider the tableaux of shape formula_163 such that the first row is given by the numbers formula_164 such that the formula_164-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