TheoremComplete

Hook Length Formula

The Hook Length Formula is a beautiful combinatorial identity that computes dimensions of irreducible representations of symmetric groups.

TheoremHook Length Formula (Frame-Robinson-Thrall)

Let Ξ»=(Ξ»1,…,Ξ»k)⊒n\lambda = (\lambda_1, \ldots, \lambda_k) \vdash n be a partition. The dimension of the corresponding irreducible representation VΞ»V^\lambda (equivalently, the number of standard Young tableaux of shape Ξ»\lambda) is: dim⁑VΞ»=fΞ»=n!∏(i,j)∈λhij\dim V^\lambda = f^\lambda = \frac{n!}{\prod_{(i,j) \in \lambda} h_{ij}} where hijh_{ij} is the hook length of the box at position (i,j)(i,j): hij=Ξ»iβˆ’j+Ξ»jβ€²βˆ’i+1h_{ij} = \lambda_i - j + \lambda_j' - i + 1 Here Ξ»jβ€²\lambda_j' is the size of column jj (the transpose partition component).

Equivalently: hijh_{ij} = (boxes to the right) + (boxes below) + 1.

ExampleComputing for $(3,2,1)$

For λ=(3,2,1)⊒6\lambda = (3,2,1) \vdash 6, the Young diagram with hook lengths: 531311\begin{matrix} 5 & 3 & 1 \\ 3 & 1 & \\ 1 & & \end{matrix}

Product of hooks: 5Γ—3Γ—1Γ—3Γ—1Γ—1=455 \times 3 \times 1 \times 3 \times 1 \times 1 = 45

Dimension: f(3,2,1)=6!45=72045=16f^{(3,2,1)} = \frac{6!}{45} = \frac{720}{45} = 16

ProofSketch via Bijections

The formula can be proved using:

  1. Combinatorial bijection: Construct a bijection between standard Young tableaux and certain factorizations
  2. Representation theory: Use character formulas and orthogonality
  3. Algebraic approach: Use the Murnaghan-Nakayama rule recursively

The classical proof uses the hook walk: a probabilistic algorithm that generates random standard Young tableaux uniformly, with probability inversely proportional to hook lengths.

β– 
TheoremDimension Sum Identity

The sum of squares of dimensions equals the group order: βˆ‘Ξ»βŠ’n(fΞ»)2=n!\sum_{\lambda \vdash n} (f^\lambda)^2 = n!

This follows from the regular representation decomposition: \mathbb{C}[S_n] \cong \bigoplus_{\lambda \vdash n} V^\lambda^{\oplus f^\lambda}

ExampleVerification for $n=3$

Partitions of 3:

  • (3)(3): hooks (3,2,1)(3,2,1), so f(3)=6/(3β‹…2β‹…1)=1f^{(3)} = 6/(3 \cdot 2 \cdot 1) = 1
  • (2,1)(2,1): hooks (3,1,1)(3,1,1), so f(2,1)=6/(3β‹…1β‹…1)=2f^{(2,1)} = 6/(3 \cdot 1 \cdot 1) = 2
  • (1,1,1)(1,1,1): hooks (3,2,1)(3,2,1), so f(1,1,1)=6/(3β‹…2β‹…1)=1f^{(1,1,1)} = 6/(3 \cdot 2 \cdot 1) = 1

Check: 12+22+12=1+4+1=6=3!1^2 + 2^2 + 1^2 = 1 + 4 + 1 = 6 = 3! βœ“

Remark

The Hook Length Formula is remarkable for:

  • Efficiency: Computes dimensions in polynomial time
  • Elegance: Pure combinatorics yields representation-theoretic invariants
  • Generalizations: Extends to affine Hecke algebras, quantum groups, and Lie type
  • Probabilistic interpretation: Relates to random matrix theory and asymptotic representation theory

No purely representation-theoretic proof avoiding combinatorics is known, suggesting deep connections between algebra and combinatorics.