Hook Length Formula
The Hook Length Formula is a beautiful combinatorial identity that computes dimensions of irreducible representations of symmetric groups.
Let be a partition. The dimension of the corresponding irreducible representation (equivalently, the number of standard Young tableaux of shape ) is: where is the hook length of the box at position : Here is the size of column (the transpose partition component).
Equivalently: = (boxes to the right) + (boxes below) + 1.
For , the Young diagram with hook lengths:
Product of hooks:
Dimension:
The formula can be proved using:
- Combinatorial bijection: Construct a bijection between standard Young tableaux and certain factorizations
- Representation theory: Use character formulas and orthogonality
- 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.
The sum of squares of dimensions equals the group order:
This follows from the regular representation decomposition: \mathbb{C}[S_n] \cong \bigoplus_{\lambda \vdash n} V^\lambda^{\oplus f^\lambda}
Partitions of 3:
- : hooks , so
- : hooks , so
- : hooks , so
Check: β
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.