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.
Definitions and statement Let λ = ( λ 1 ≥ ⋯ ≥ λ k ) {\displaystyle \lambda =(\lambda _{1}\geq \cdots \geq \lambda _{k})} be a partition of n = λ 1 + ⋯ + λ k {\displaystyle n=\lambda _{1}+\cdots +\lambda _{k}} . It is customary to interpret λ {\displaystyle \lambda } graphically as a Young diagram, namely a left-justified array of square cells with k {\displaystyle k} rows of lengths λ 1 , … , λ k {\displaystyle \lambda _{1},\ldots ,\lambda _{k}} . A (standard) Young tableau of shape λ {\displaystyle \lambda } is a filling of the n {\displaystyle n} cells of the Young diagram with all the integers { 1 , … , n } {\displaystyle \{1,\ldots ,n\}} , with no repetition, such that each row and each column form increasing sequences. For the cell in position ( i , j ) {\displaystyle (i,j)} , in the i {\displaystyle i} th row and j {\displaystyle j} th column, the hook H λ ( i , j ) {\displaystyle H_{\lambda }(i,j)} is the set of cells ( a , b ) {\displaystyle (a,b)} such that a = i {\displaystyle a=i} and b ≥ j {\displaystyle b\geq j} or a ≥ i {\displaystyle a\geq i} and b = j {\displaystyle b=j} . The hook length h λ ( i , j ) {\displaystyle h_{\lambda }(i,j)} is the number of cells in H λ ( i , j ) {\displaystyle H_{\lambda }(i,j)} . The hook length formula expresses the number of standard Young tableaux of shape λ {\displaystyle \lambda } , denoted by f λ {\displaystyle f^{\lambda }} or d λ {\displaystyle d_{\lambda }} , as
f λ = n ! ∏ h λ ( i , j ) , {\displaystyle f^{\lambda }={\frac {n!}{\prod h_{\lambda }(i,j)}},}
where the product is over all cells ( i , j ) {\displaystyle (i,j)} of the Young diagram.
Examples
The figure on the right shows hook lengths for the cells in the Young diagram λ = ( 4 , 3 , 1 , 1 ) {\displaystyle \lambda =(4,3,1,1)} , corresponding to the partition 9 = 4 + 3 + 1 + 1. The hook length formula gives the number of standard Young tableaux as:
f λ = 9 ! 7 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 2 ⋅ 1 ⋅ 1 ⋅ 1 = 216. {\displaystyle f^{\lambda }={\frac {9!}{7\cdot 5\cdot 4\cdot 3\cdot 2\cdot 2\cdot 1\cdot 1\cdot 1}}=216.}
… excerpt ends here. Continue reading the full article.
