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. A related formula gives the number of semi-standard Young tableaux, which is a specialization of a Schur polynomial.
Let
λ=(λ1\geq … \geqλk)
n=λ1+ … +λk
λ
k
λ1,\ldots,λk
λ
n
\{1,\ldots,n\}
(i,j)
i
j
Hλ(i,j)
(a,b)
a=i
b\gej
a\gei
b=j
hλ(i,j)
Hλ(i,j)
The hook length formula expresses the number of standard Young tableaux of shape
λ
fλ
dλ
fλ=
n! | |
\prodhλ(i,j) |
,
(i,j)
λ=(4,3,1,1)
fλ=
9! | |
7 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 2 ⋅ 1 ⋅ 1 ⋅ 1 |
=216.
Cn
n
n
λ=(n,n)
This shows that
Cn=f(n,n)
Cn=
(2n)! | |
(n+1)(n) … (3)(2)(n)(n-1) … (2)(1) |
=
(2n)! | |
(n+1)!n! |
=
1 | |
n{+ |
1}\binom{2n}{n}.
There are other formulas for
fλ
fλ
The hook length formula itself was discovered in 1953 by Frame, Robinson, and Thrall as an improvement to the Young–Frobenius formula. Sagan[4] describes the discovery as follows.
Despite the simplicity of the hook length formula, the Frame–Robinson–Thrall proof is not very insightful and does not provide any intuition for the role of the hooks. The search for a short, intuitive explanation befitting such a simple result gave rise to many alternate proofs.[5] Hillman and 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.[6] Greene, Nijenhuis, and Wilf found a probabilistic proof using the hook walk in which the hook lengths appear naturally in 1979.[7] Remmel adapted the original Frame–Robinson–Thrall proof into the first bijective proof for the hook length formula in 1982.[8] A direct bijective proof was first discovered by Franzblau and Zeilberger in 1982.[9] Zeilberger also converted the Greene–Nijenhuis–Wilf hook walk proof into a bijective proof in 1984.[10] A simpler direct bijection was announced by Pak and Stoyanovskii in 1992, and its complete proof was presented by the pair and Novelli in 1997.[11] [12] [4]
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.[13] Sagan gave a shifted hook walk proof for the hook length formula for shifted Young tableaux in 1980.[14] Sagan and Yeh proved the hook length formula for binary trees using the hook walk in 1989.[15] Proctor gave a poset generalization (see below).
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
(i,j)
i
j
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.[7] Define
eλ=
n! | |
\prod(i,j)\inhλ(i,j) |
.
We wish to show that
fλ=eλ
fλ=\sum\mu\uparrowλf\mu,
where the sum runs over all Young diagrams
\mu
λ
λ
\mu
We define
f\emptyset=1
e\emptyset=1
eλ=\sum\mu\uparrowλe\mu,
which would imply
λ=e | |
f | |
λ |
\sum\mu\uparrowλ
e\mu | |
eλ |
=1.
We therefore need to show that the numbers
e\mu | |
eλ |
\mu
\mu\uparrowλ
λ
λ
\mu
\mu\uparrowλ
|λ|
(i,j)
Hλ(i,j)\setminus\{(i,j)\}
bf{c}
Proposition: For a given corner cell
(a,b)
λ
P\left(
|
where
\mu=λ\setminus\{(a,b)\}
Given this, summing over all corner cells
(a,b)
\sum\mu\uparrowλ
e\mu | |
eλ |
=1
Sn
fλ
Vλ
λ
The complex irreducible representations
Vλ
λ
n
\chiλ(w)=\langlesλ,p\tau(w)\rangle,
where
sλ
λ
p\tau(w)
\tau(w)
w
w=(154)(238)(6)(79)
\tau(w)=(3,3,2,1)
Since the identity permutation
e
e=(1)(2) … (n)
\tau(e)=(1,\ldots,1)=1(n)
fλ=\dimVλ=\chiλ(e)=\langlesλ,
p | |
1(n) |
\rangle
The expansion of Schur functions in terms of monomial symmetric functions uses the Kostka numbers:
sλ=\sum\muKλ\mum\mu,
Then the inner product with
p | |
1(n) |
=
h | |
1(n) |
K | |
λ1(n) |
\langlem\mu,h\nu\rangle=\delta\mu\nu
K | |
λ1(n) |
fλ=\dimVλ
style\sumλ\vdash\left(fλ\right)2=n!
Sn
The computation also shows that:
(x1+x2+ … +x
n | |
k) |
=\sumλ\vdashsλfλ.
This is the expansion of
p | |
1(n) |
\langles\mu,s\nu\rangle=\delta\mu\nu
V ⊗
GL(V)
Source:[17]
By the above considerations
p | |
1(n) |
=\sumλ\vdashsλfλ
so that
\Delta(x)p | |
1(n) |
=\sumλ\vdash\Delta(x)sλfλ
\Delta(x)=\prodi<j(xi-xj)
For the partition
λ=(λ1\geq … \geqλk)
li=λi+k-i
i=1,\ldots,k
n
x1, … ,xn
Each term
\Delta(x)sλ
a | |
(λ1+k-1,λ2+k-2,...,λk) |
(x1,x2,...,xk) = \det\left[\begin{matrix}
l1 | |
x | |
1 |
&
l1 | |
x | |
2 |
&...&
l1 | |
x | |
k |
l2 | |
\\ x | |
1 |
&
l2 | |
x | |
2 |
&...&
l2 | |
x | |
k |
\\ \vdots&\vdots&\ddots&\vdots
lk | |
\\ x | |
1 |
&
lk | |
x | |
2 |
&...&
lk | |
x | |
k |
\end{matrix}\right]
(See Schur function.) Since the vector
(l1,\ldots,lk)
l1 | |
x | |
1 |
…
lk | |
x | |
k |
\Delta(x)p | |
1(n) |
\left[\Delta(x)p | |
1(n) |
\right] | |
l1, … ,lk |
fλ
It remains only to simplify this coefficient. Multiplying
\Delta(x)
= \sum | |
w\inSn |
sgn(w)
w(1)-1 | |
x | |
1 |
w(2)-1 | |
x | |
2 |
…
w(k)-1 | |
x | |
k |
and
p | |
1(n) |
= (x1+x2+ … +x
n | |
k) |
= \sum
n! | |
d1!d2! … dk! |
d1 | |
x | |
1 |
d2 | |
x | |
2 |
…
dk | |
x | |
k |
we conclude that our coefficient as
\sum | sgn(w) | |
w\inSn |
n! | |
(l1-w(1)+1)! … (lk-w(k)+1)! |
which can be written as
n! | |
l1!l2! … lk! |
\sum | |
w\inSn |
sgn(w)\left[(l1)(l1-1) … (l1-w(1)+2)\right]\left[(l2)(l2-1) … (l2-w(2)+2)\right]\left[(lk)(lk-1) … (lk-w(k)+2)\right]
The latter sum is equal to the following determinant
\det\left[\begin{matrix}1&l1&l1(l1-1)&...&
k-2 | |
\prod | |
i=0 |
(l1-i)\\ 1&l2&l2(l2-1)&...&
k-2 | |
\prod | |
i=0 |
(l2-i)\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&lk&lk(lk-1)&...&
k-2 | |
\prod | |
i=0 |
(lk-i)\end{matrix}\right]
which column-reduces to a Vandermonde determinant, and we obtain the formula
fλ=
n! | |
l1!l2! … lk! |
\prodi<j(li-lj).
Note that
li
n! | |
\prodhλ(i,j) |
styleli!=\prodj(li-lj) ⋅
\prod | |
j\leqλi |
hλ(i,j)
i
The hook length formula also has important applications to the analysis of longest increasing subsequences in random permutations. If
\sigman
n
L(\sigman)
\sigman
\elln
L(\sigman)
n
\elln
2\sqrt{n}
fλ
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
fλ
The formula for the number of Young tableaux of shape
λ
f(λ1,\ldots,λk)=
n!\Delta(λk,λk-1+1,\ldots,λ1+k-1) | |
λk!(λk-1+1)! … (λ1+k-1)! |
.
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
h1,...,hp
infty | |
\sum | |
n=0 |
\pinxn=
p | |
\prod | |
k=1 |
hk | |
(1-x |
)-1
Stanley discovered another formula for the same generating function.[20] In general, if
A
n
A
P(x) | |
(1-x)(1-x2) … (1-xn) |
where
P(x)
P(1)
A
In the case of a partition
λ
(i,j)\leq(i',j')\iffi\leqi' rm{and} j\leqj'
So a linear extension is simply a standard Young tableau, i.e.
P(1)=fλ
Combining the two formulas for the generating functions we have
P(x) | |
(1-x)(1-x2) … (1-xn) |
=\prod(i,j)\in
h(i,j) | |
(1-x |
)-1
Both sides converge inside the disk of radius one and the following expression makes sense for
|x|<1
P(x)=
| ||||||||||
|
.
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
P(1)=\limx\to
| ||||||||||
|
.
n
P(1)=
n! | |
\prod(i,j)\inh(i,j) |
.
sλ(x1,\ldots,xk)
λ
\{1,\ldots,k\}
xi=1
The Young diagramsλ(1,\ldots,1) = \prod(i,j)\in
k-i+j hλ(i,j) .
λ
SLk(C)
diag(x1,\ldots,xk)
We may refine this by taking the principal specialization of the Schur function in the variables
1,t,t2,t3,\ldots
sλ(1,t,t2,\ldots) =
tn\left( | ||||||||||
|
,
where
n(λ)=\sumi(i{-}1)λi=\sumi\tbinom{λi'}{2}
λ'
There is a generalization of this formula for skew shapes,[21]
sλ/\mu(1,t,t2, … )=\sumS\prod(i,j)
| |||||
1-th(i,j) |
λ
\mu
A variation on the same theme is given by Okounkov and Olshanski[22] of the form
\dimλ/\mu | = | |
\dimλ |
| |||||||
|λ|!/|\mu|! |
,
* | |
s | |
\mu |
* | |
s | |
\mu(x |
1,...,x
|
Young diagrams can be considered as finite order ideals in the poset
N x N