Young Diagrams and Partitions

The representation theory of the symmetric group $S_n$ has beautiful combinatorial structure, with irreducible representations indexed by partitions and constructed using Young diagrams.

DefinitionPartition

A partition of $n$ is a non-increasing sequence $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_k)$ of positive integers summing to $n$ : $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k > 0, \quad \sum_{i=1}^k \lambda_i = n$

We write $\lambda \vdash n$ to denote that $\lambda$ is a partition of $n$ . The number of parts is the length $\ell(\lambda) = k$ .

ExamplePartitions of 4

The partitions of 4 are:

$(4)$ — one part
$(3,1)$ — two parts
$(2,2)$ — equal parts
$(2,1,1)$ — three parts
$(1,1,1,1)$ — four parts

There are $p(4) = 5$ partitions of 4, where $p(n)$ is the partition function.

DefinitionYoung Diagram

The Young diagram (or Ferrers diagram) of a partition $\lambda = (\lambda_1, \ldots, \lambda_k)$ is an arrangement of boxes in left-justified rows, with row $i$ containing $\lambda_i$ boxes.

For example, $(3,2,1) \vdash 6$ has Young diagram: $\begin{matrix} \Box & \Box & \Box \\ \Box & \Box & \\ \Box & & \end{matrix}$

DefinitionYoung Tableau

A Young tableau of shape $\lambda$ is a filling of the Young diagram with numbers. A standard Young tableau (SYT) is a filling with $1, 2, \ldots, n$ (each used once) such that:

Rows are strictly increasing from left to right
Columns are strictly increasing from top to bottom

The number of standard Young tableaux of shape $\lambda$ is denoted $f^\lambda$ .

ExampleStandard Young Tableaux of $(2,1)$

For $\lambda = (2,1) \vdash 3$ , the standard Young tableaux are: $\begin{matrix} 1 & 2 \\ 3 & \end{matrix} \quad \text{and} \quad \begin{matrix} 1 & 3 \\ 2 & \end{matrix}$

Thus $f^{(2,1)} = 2$ .

TheoremDimension Formula (Hook Length Formula)

The dimension of the irreducible representation $V^\lambda$ of $S_n$ corresponding to partition $\lambda$ is: $\dim V^\lambda = f^\lambda = \frac{n!}{\prod_{\square \in \lambda} h(\square)}$ where $h(\square)$ is the hook length of box $\square$ : the number of boxes directly to the right, directly below, plus 1 (for the box itself).

ExampleComputing Hook Lengths

For $\lambda = (3,2)$ : $\begin{matrix} 5 & 3 & 1 \\ 3 & 1 & \end{matrix}$

The hook lengths are shown. Thus: $f^{(3,2)} = \frac{5!}{5 \cdot 3 \cdot 1 \cdot 3 \cdot 1} = \frac{120}{45} = \frac{8}{3} \cdot 3 = 5$

Wait, let me recalculate: $5 \times 3 \times 1 \times 3 \times 1 = 45$ , and $120/45 = 8/3$ . Actually $(3,2) \vdash 5$ , so $5!= 120$ and the product is $5 \cdot 3 \cdot 1 \cdot 3 \cdot 1 = 45$ , giving $f^{(3,2)} = 120/45 \approx 2.67$ ... Let me recalculate hook lengths.

For $(3,2)$ : First row has hooks $(4,3,2)$ and second row has hooks $(2,1)$ . Product: $4 \times 3 \times 2 \times 2 \times 1 = 48$ . Thus $f^{(3,2)} = 120/48 = 2.5$ .

Actually for $\lambda = (3,2) \vdash 5$ : hooks are $\begin{matrix} 4 & 3 & 1 \\ 2 & 1 & \end{matrix}$ . Product is $4 \times 3 \times 1 \times 2 \times 1 = 24$ , giving $f^{(3,2)} = 120/24 = 5$ .

Remark

The correspondence between partitions and irreducible representations of $S_n$ is one of the most beautiful results in representation theory. The combinatorics of Young diagrams encodes deep algebraic structure, connecting representation theory to algebraic combinatorics, symmetric functions, and mathematical physics.