Hook length formula

The hook length formula can be understood intuitively using the following heuristic, but incorrect, argument suggested by D. E. Knuth.[17] Given that each element of a tableau is the smallest in its hook and filling the tableau shape at random, the probability that cell ${\displaystyle (i,j)}$ will contain the minimum element of the corresponding hook is the reciprocal of the hook length. Multiplying these probabilities over all ${\displaystyle i}$ and ${\displaystyle 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.

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

${\displaystyle e_{\lambda }={\frac {n!}{\prod _{(i,j)\in Y(\lambda )}h_{\lambda }(i,j)}}.}$

We wish to show that ${\displaystyle f^{\lambda }=e_{\lambda }}$. First,

${\displaystyle f^{\lambda }=\sum _{\mu \uparrow \lambda }f^{\mu },}$

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

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

We define ${\displaystyle f^{\emptyset }=1}$and ${\displaystyle e_{\emptyset }=1}$, so it is enough to show the same recurrence

${\displaystyle e_{\lambda }=\sum _{\mu \uparrow \lambda }e_{\mu },}$

which would imply ${\displaystyle f^{\lambda }=e_{\lambda }}$ by induction. The above sum can be viewed as a sum of probabilities by writing it as

${\displaystyle \sum _{\mu \uparrow \lambda }{\frac {e_{\mu }}{e_{\lambda }}}=1.}$

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

1. Pick a cell uniformly at random from ${\displaystyle |\lambda |}$ cells. Start the random walk from there.
2. Successor of current cell ${\displaystyle (i,j)}$ is chosen uniformly at random from the hook ${\displaystyle H_{\lambda }(i,j)\setminus \{(i,j)\}}$.
3. Continue until you reach a corner cell ${\displaystyle {\textbf {c}}}$.

Proposition: For a given corner cell ${\displaystyle (a,b)}$ of ${\displaystyle \lambda }$, we have

${\displaystyle \mathbb {P} \left({\textbf {c}}=(a,b)\right)={\frac {e_{\mu }}{e_{\lambda }}},}$

where ${\displaystyle \mu =\lambda \setminus \{(a,b)\}}$.

Given this, summing over all corner cells ${\displaystyle (a,b)}$ gives ${\displaystyle \sum _{\mu \uparrow \lambda }{\frac {e_{\mu }}{e_{\lambda }}}=1}$ as claimed.

The complex irreducible representations ${\displaystyle V_{\lambda }}$ of the symmetric group are indexed by partitions ${\displaystyle \lambda }$ of ${\displaystyle n}$ (see Specht module) . Their characters are related to the theory of symmetric functions via the Hall inner product:

${\displaystyle \chi ^{\lambda }(w)=\langle s_{\lambda },p_{\tau (w)}\rangle ,}$

where ${\displaystyle s_{\lambda }}$ is the Schur function associated to ${\displaystyle \lambda }$ and ${\displaystyle p_{\tau (w)}}$ is the power-sum symmetric function of the partition ${\displaystyle \tau (w)}$ associated to the cycle decomposition of ${\displaystyle w}$. For example, if ${\displaystyle w=(154)(238)(6)(79)}$ then ${\displaystyle \tau (w)=(3,3,2,1)}$.

Since the identity permutation ${\displaystyle e}$ has the form ${\displaystyle e=(1)(2)\cdots (n)}$ in cycle notation, ${\displaystyle \tau (e)=(1,\ldots ,1)=1^{(n)}}$, the formula says

${\displaystyle f^{\lambda }\,=\,\dim V_{\lambda }\,=\,\chi ^{\lambda }(e)\,=\,\langle s_{\lambda },p_{1^{(n)}}\rangle }$

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

${\displaystyle s_{\lambda }=\sum _{\mu }K_{\lambda \mu }m_{\mu },}$

Then the inner product with ${\displaystyle p_{1^{(n)}}=h_{1^{(n)}}}$ is ${\displaystyle K_{\lambda 1^{(n)}}}$, because ${\displaystyle \langle m_{\mu },h_{\nu }\rangle =\delta _{\mu \nu }}$. Note that ${\displaystyle K_{\lambda 1^{(n)}}}$ is equal to ${\displaystyle f^{\lambda }=\dim V_{\lambda }}$, so that ${\displaystyle \textstyle \sum _{\lambda \vdash n}\left(f^{\lambda }\right)^{2}=n!}$ from considering the regular representation of ${\displaystyle S_{n}}$, or combinatorially from the Robinson–Schensted–Knuth correspondence.

The computation also shows that:

${\displaystyle (x_{1}+x_{2}+\cdots +x_{k})^{n}=\sum _{\lambda \vdash n}s_{\lambda }f^{\lambda }.}$

This is the expansion of ${\displaystyle p_{1^{(n)}}}$ in terms of Schur functions using the coefficients given by the inner product, since ${\displaystyle \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 ${\displaystyle V^{\otimes n}}$ by irreducible ${\displaystyle GL(V)}$ modules, and taking characters. See Schur–Weyl duality.

By the above considerations

${\displaystyle p_{1^{(n)}}=\sum _{\lambda \vdash n}s_{\lambda }f^{\lambda }}$

so that

${\displaystyle \Delta (x)p_{1^{(n)}}=\sum _{\lambda \vdash n}\Delta (x)s_{\lambda }f^{\lambda }}$

where ${\displaystyle \Delta (x)=\prod _{i<j}(x_{i}-x_{j})}$ is the Vandermonde determinant.

For the partition ${\displaystyle \lambda =(\lambda _{1}\geq \cdots \geq \lambda _{k})}$, define ${\displaystyle l_{i}=\lambda _{i}+k-i}$ for ${\displaystyle i=1,\ldots ,k}$. For the following we need at least as many variables as rows in the partition, so from now on we work with ${\displaystyle n}$ variables ${\displaystyle x_{1},\cdots ,x_{n}}$.

Each term ${\displaystyle \Delta (x)s_{\lambda }}$ is equal to

${\displaystyle 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 ${\displaystyle (l_{1},\ldots ,l_{k})}$ is different for each partition, this means that the coefficient of ${\displaystyle x_{1}^{l_{1}}\cdots x_{k}^{l_{k}}}$ in ${\displaystyle \Delta (x)p_{1^{(n)}}}$, denoted ${\displaystyle \left[\Delta (x)p_{1^{(n)}}\right]_{l_{1},\cdots ,l_{k}}}$, is equal to ${\displaystyle f^{\lambda }}$. This is known as the Frobenius Character Formula, which gives one of the earliest proofs.[20]

It remains only to simplify this coefficient. Multiplying

${\displaystyle \Delta (x)\ =\ \sum _{w\in S_{n}}\operatorname {sgn}(w)x_{1}^{w(1)-1}x_{2}^{w(2)-1}\cdots x_{k}^{w(k)-1}}$

and

${\displaystyle 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 our coefficient as

${\displaystyle \sum _{w\in S_{n}}\operatorname {sgn}(w){\frac {n!}{(l_{1}-w(1)+1)!\cdots (l_{k}-w(k)+1)!}}}$

which can be written as

${\displaystyle {\frac {n!}{l_{1}!l_{2}!\cdots l_{k}!}}\sum _{w\in S_{n}}\operatorname {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

${\displaystyle \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 a Vandermonde determinant, and we obtain the formula

${\displaystyle f^{\lambda }\ =\ {\frac {n!}{l_{1}!l_{2}!\cdots l_{k}!}}\prod _{i<j}(l_{i}-l_{j}).}$

Note that ${\displaystyle l_{i}}$ 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 ${\displaystyle {\frac {n!}{\prod h_{\lambda }(i,j)}}}$: one shows ${\displaystyle \textstyle l_{i}!\ =\ \prod _{j>i}(l_{i}-l_{j})\cdot \prod _{j\leq \lambda _{i}}h_{\lambda }(i,j)}$, where the latter product runs over the ${\displaystyle i}$th row of the Young diagram.

Combining the two formulas for the generating functions we have

${\displaystyle {\frac {P(x)}{(1-x)(1-x^{2})\cdots (1-x^{n})}}=\prod _{(i,j)\in \lambda }(1-x^{h_{(i,j)}})^{-1}}$

Both sides converge inside the disk of radius one and the following expression makes sense for ${\displaystyle |x|<1}$

${\displaystyle P(x)={\frac {\prod _{k=1}^{n}(1-x^{k})}{\prod _{(i,j)\in \lambda }(1-x^{h_{(i,j)}})}}.}$

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

${\displaystyle P(1)=\lim _{x\to 1}{\frac {\prod _{k=1}^{n}(1-x^{k})}{\prod _{(i,j)\in \lambda }(1-x^{h_{(i,j)}})}}.}$

Applying L'Hôpital's rule ${\displaystyle n}$ times yields the hook length formula

${\displaystyle P(1)={\frac {n!}{\prod _{(i,j)\in \lambda }h_{(i,j)}}}.}$

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

${\displaystyle s_{\lambda /\mu }(1,t,t^{2},\cdots )=\sum _{S\in E(\lambda /\mu )}\prod _{(i,j)\in \lambda \setminus S}{\frac {t^{\lambda _{j}'-i}}{1-t^{h(i,j)}}}}$

where the sum is taken over excited diagrams of shape ${\displaystyle \lambda }$ and boxes distributed according to ${\displaystyle \mu }$.