フック長の公式
数学の組合せ論において、フック長の公式(フックちょうのこうしき、Hook length formula)とは、与えられたヤング図形の形をした標準盤を数える公式である。表現論や、確率論、アルゴリズム解析などの多種多様な分野に応用があり、最長増加部分列問題などが例としてあげられる。
Let \lambda=(\lambda_1,\ldots,\lambda_m) be a partition of n. It is customary to interpret \lambda graphically as a Young diagram, namely a left-justified array of square cells with m rows and \lambda_i cells in the ith row for each 1\le i\le m. A standard Young tableau of shape \lambda is a Young diagram of shape \lambda 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 of the Young diagram in coordinates (i,j) (that is, the cell in the ith row and jth column), the hook H_\lambda(i,j) is the set of cells (a,b) such that a=i and b \ge j or a \ge i and b=j. The hook-length h_\lambda(i,j) is the number of cells in the hook H_\lambda(i,j).
Then the hook-length formula expresses the number of standard Young tableaux of shape \lambda, sometimes denoted by d_\lambda, as
d_\lambda = \frac{n!}{\prod h_\lambda (i,j)} ,
where the product is over all cells (i,j) of \lambda.
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 d_\lambda for this Young diagram can be computed as
d_\lambda = \frac{9!}{7\cdot 5\cdot 4\cdot 3\cdot 2\cdot 2\cdot 1\cdot 1\cdot 1} = 216.
There are other formulas for d_\lambda, 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 d_\lambda 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.
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 (i,j) will contain the minimum element of the corresponding hook is the reciprocal of the hook length.  Multiplying these probabilities over all i and j 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 によって発見された、確率論的証明法である。証明の概略は、次のとおりである。
e_\lambda = \frac{n!}{\prod_{(i,j)\in Y(\lambda)}h_\lambda(i,j)}.
を定義し、 d_\lambda = e_\lambdaを証明する。
d_\lambdaは以下で与えられる。
d_\lambda = \sum_{\mu\uparrow\lambda}d_\mu,
ここで、 \mu\uparrow\lambda は、\muがヤング図形λから一つのコーナーセルを削除することで得られるヤングタブローであることを表している。
そのようなμの全体にわたって和をとる。ここで、慣習として \phiを空のダイアグラムとして、 d_{\phi}=1を用いる。
上の式に対する説明は、「ヤングタブローの最大項はそのコーナーセルで生じるものである」となる。
そのセルを削除することで、μの形のヤングタブローを得る。
μの形のヤングタブローの数が  d_{\mu}であり、それらμに関して和をとることでその式を得る。
ここで、e_{\phi}=1であることにも注意されたい。それゆえ、次を示せば十分で、
e_\lambda = \sum_{\mu\uparrow\lambda}e_\mu,
その結果、 d_\lambda=e_\lambda は帰納的に証明される。
上の式の和は、次のように式を書き換えることによって、確率の和と捉えることができる。
\sum_{\mu\uparrow\lambda}\frac{e_\mu}{e_\lambda}=1.
われわれはこのようにして、 \frac{e_\mu}{e_\lambda}が、ヤング図形μの集合上の確率測度を定めている。(ここで \mu\uparrow\lambda)
これはフックウォークと呼ばれるランダムウォークを定義を用いた構成法によるものである。
フックウォークは、ヤング図形λの上で、ひとつのコーナーセルを選択する。
フックウォークは次のルールによって定義される。
(1)  |\lambda| 個のセルのなかから一様ランダムにひとつのセルを選び、そこからランダムウォークを始める。
(2) 現在の (i,j)セルの次のセルは、一様ランダムにフック H_{\lambda}(i,j)\setminus \{(i,j)\}から選ぶ。
(3) 一つのコーナーに到達するまでこれを続け、そのコーナーセルを\textbf{c}とする。
命題: λに属するすべてのコーナーセル (a,b)に対して、次が成り立つ。
\mathbb{P}\left(\textbf{c}=(a,b)\right)=\frac{e_\mu}{e_\lambda},
ここで、 \mu=\lambda\setminus\{(a,b)\}.
この命題を得れば、すべての \textbf{c}=(a,b) に関して和をとることによって、  \sum_{\mu\uparrow\lambda}\frac{e_{\mu}{e_{\lambda}=1を得る。
The hook-length formula is of great importance in the representation theory of the symmetric group S_n, where the number d_\lambda is known to be equal to the dimension of the complex irreducible representation V_\lambda associated to \lambda, and is frequently denoted by \dim V_\lambda, \dim \lambda or f^\lambda.
The complex irreducible representations  V_{\lambda}  of the symmetric group are indexed by partitions  \lambda  of  n  (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
\chi^\lambda(w)=\langle s_\lambda, p_{\tau(w)}\rangle
where  s_{\lambda}  is the Schur function associated to  \lambda  and  p_{\tau(w)}  is the power-sum symmetric function of the partition  \tau(w)  associated to the cycle decomposition of  w . For example, if  w=(154)(238)(6)(79)  then  \tau(w) = (3,3,2,1) .
Since the identity permutation e has the form  e=(1)(2)\cdots(n)  in cycle notation,  \tau(e) = 1+1+\cdots+1=1^{(n)} . Then the formula says
\dim  V_\lambda =\chi^\lambda(e) = \langle s_\lambda, p_{1^{(n)}\rangle
Considering the expansion of Schur functions in terms of monomial symmetric functions using the Kostka numbers
s_\lambda= \sum_\mu K_{\lambda\mu}m_\mu,
the inner product with  p_{1^{(n)} = h_{1^{(n)}  is   K_{\lambda 1^{(n)} , because   \langle m_{\mu},h_{\nu} \rangle = \delta_{\mu\nu} . Note that  K_{\lambda 1^{(n)}   is equal to  d_{\lambda} . Hence
\dim V_\lambda = d_\lambda.
An immediate consequence of this is
\sum_{\lambda\vdash n} \left(f^{\lambda}\right)^2 = n!
The above equality is also a simple consequence of the Robinson–Schensted–Knuth correspondence.
The computation also shows that:
(x_1+x_2+\cdots+x_k)^n = \sum_{\lambda\vdash n} s_\lambda f^\lambda.
Which is the expansion of   p_{1^{(n)}  in terms of Schur functions using the coefficients given by the inner product, because  \langle s_{\mu},s_{\nu}\rangle = \delta_{\mu\nu}  . 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 V^{\otimes n}  by irreducible   GL(V)  modules, and taking characters. See Schur–Weyl duality.
By the above considerations
p_{1^{(n)} =  \sum_{\lambda\vdash n} s_{\lambda}f^{\lambda}
So that
\Delta(x)p_{1^{(n)} = \sum_{\lambda\vdash n} \Delta(x)s_{\lambda}f^{\lambda}
where   \Delta(x) = \prod_{i<j} (x_i-x_j) is the Vandermonde determinant.
For a given partition  \lambda = (\lambda_1, \lambda_2, \cdots, \lambda_k)  define  l_i = \lambda_i+k-i  for  i=1,2,\cdots,k . For the following we need at least as many variables as rows in the partition, so from now on we work with n  variables x_1,\cdots,x_n.
Each term  \Delta(x)s_{\lambda}   is equal to
a_{(\lambda_1+k-1, \lambda_2+k-2, \dots , \lambda_k)} (x_1, x_2, \dots , x_k) =
\det \left[ \begin{matrix} x_1^{l_1} & x_2^{l_1} & \dots & x_k^{l_1} \\
x_1^{l_2} & x_2^{l_2} & \dots & x_k^{l_2} \\
\vdots & \vdots & \ddots & \vdots \\
x_1^{l_k} & x_2^{l_k} & \dots & x_k^{l_k} \end{matrix} \right]
See Schur function. Since the vector  (l_1,l_2,\cdots, l_k)  is different for each partition, this means that the coefficient of   x_1^{l_1}\cdots x_k^{l_k}  in \Delta(x)p_{1^{(n)}, denoted \left[\Delta(x)p_{1^{(n)}\right]_{l_1,\cdots,l_k}, is equal to  f^{\lambda} . 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
\Delta(x) = \sum_{w\in S_n}  \sgn(w) x_1^{w(1)-1}x_2^{w(2)-1}\cdots x_k^{w(k)-1}
p_{1^{(n)} = (x_1+x_2+\cdots+x_k)^n = \sum \frac{n!}{d_1!d_2!\cdots d_k!} x_1^{d_1}x_2^{d_2}\cdots x_k^{d_k}
we conclude that the coefficient that we are looking for is
\sum_{w\in S_n} \sgn(w)\frac{n!}{(l_1-w(1)+1)!(l_2-w(2)+1)!\cdots (l_k-w(k)+1)!}
which can be written as
\frac{n!}{l_1!l_2!\cdots l_k!} \sum_{w\in S_n} \sgn(w)\left[(l_1)(l_1-1)\cdots(l_1-w(1)+2)\right] \left[(l_2)(l_2-1)\cdots(l_2-w(2)+2)\right]\left[(l_k)(l_k-1)\cdots(l_k-w(k)+2)\right]
The latter sum is equal to the following determinant
\det \left[ \begin{matrix} 1 & l_1 & l_1(l_1-1) & \dots & \prod_{i=0}^{k-2} (l_1-i) \\
1 & l_2 & l_2(l_2-1) & \dots & \prod_{i=0}^{k-2} (l_2-i)\\
\vdots & \vdots & \vdots& \ddots & \vdots \\
1 & l_k & l_k(l_k-1) & \dots & \prod_{i=0}^{k-2} (l_k-i) \end{matrix} \right]
which column reduces to the Vandermonde determinant, and we obtain the formula
d_\lambda = \frac{n!}{l_1!l_2!\cdots l_k!} \prod_{i<j} (l_i-l_j)
Note that  l_i  is the hook length of the first box in each row of the Young Diagram. Transforming this expression into the form  \frac{n!}{\prod h_\lambda (i,j)}  claimed by the hook-length formula is a fairly simple exercise in combinatorics: For any given  i = 1, 2, \ldots, k , one has to argue that  l_i! = \left(\prod_{j > i} (l_i - l_j)\right) \cdot \prod_c h_\lambda(c) , where the latter product ranges over all cells c in the i-row of the Young diagram of \lambda.
The hook length formula also has important applications to the analysis of longest increasing subsequences in random permutations. If \sigma_n denotes a uniformly random permutation of order n, L(\sigma_n) denotes the maximal length of an increasing subsequence of \sigma_n, and \ell_n denotes the expected (average) value of L(\sigma_n), Anatoly Vershik and Sergei Kerov  and independently Benjamin F. Logan and Lawrence A. Shepp  showed that when n is large, \ell_n is approximately equal to 2 \sqrt{n}. 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 d_\lambda, the hook length formula can then be used to perform an asymptotic analysis of the limit shape and thereby also answer the original question.