Murnaghan-Nakayama rule

Intuition [Beginner]

Every irreducible representation of the symmetric group $S_n$ is labelled by a Young diagram — a pattern of boxes arranged in left-justified rows. The character of a representation is a list of numbers, one for each conjugacy class, that tells you how the representation behaves.

The Murnaghan-Nakayama rule is a procedure for computing these character numbers using only the picture of the Young diagram. Here is how it works: to compute the character value for a permutation with cycle type $({\mu }_1,{\mu }_2,\dots )$, you remove a connected strip of ${\mu }_1$ boxes from the border (the outer edge) of the diagram. Each way of removing such a strip contributes a signed value. Then you repeat with ${\mu }_2$ on the smaller diagram, and so on.

Why does this concept exist? Because the character values of $S_n$ have an elegant combinatorial description that avoids all algebra — you just draw diagrams, remove strips, count rows, and add up signs.

Visual [Beginner]

The picture shows the Young diagram of the partition $(4,3,1)$ with a border strip of length $3$ highlighted in dark shading. The strip winds along the outer edge of the diagram, occupying $2$ rows. Its height is $1$ (number of rows minus one), so it contributes a sign of $(-1{)}^1=-1$.

A border strip is a connected ribbon of boxes along the rim of the diagram, with at most one box in each column and at most one box in each row of the strip.

Worked example [Beginner]

Compute ${\chi }^{(3,2)}(\mu )$ for $S_5$ where $\mu =(3,2)$.

Step 1. Start with the Young diagram of $\lambda =(3,2)$. Find all border strips of length ${\mu }_1=3$. A border strip of length $3$ is a connected ribbon of $3$ boxes along the outer edge.

Step 2. There are two such strips: (a) remove the last $3$ boxes from the first row (leaving diagram $(0,2)$, but that is not a valid partition, so this strip does not work — we need a connected border strip). Re-examine: the valid border strips of length $3$ in $(3,2)$ are: (i) the top-right $2$ boxes of row $1$ plus the rightmost box of row $2$, giving a strip in $2$ rows with height $1$; (ii) the top-right $1$ box of row $1$ plus both boxes of row $2$, giving a strip in $2$ rows with height $1$.

Step 3. For strip (i): height $=1$, sign $=-1$, remaining diagram $=(2,1)$. For strip (ii): height $=1$, sign $=-1$, remaining diagram $=(2,1)$. Now recurse: compute ${\chi }^{(2,1)}(2)$ for $S_3$. The border strips of length $2$ in $(2,1)$ are: one strip (the two boxes in row $1$), height $0$, sign $+1$, remaining diagram $(0,1)=(1)$. So ${\chi }^{(2,1)}(2)=+1\cdot {\chi }^{(1)}()=1$.

What this tells us: ${\chi }^{(3,2)}(3,2)=(-1)(1)+(-1)(1)=-2$.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Let $\lambda$ be a partition of $n$ (written $\lambda ⊢n$), represented by its Young diagram. A border strip (also called a rim hook) of length $k$ in $\lambda$ is a connected subset $\xi$ of $k$ boxes in the diagram such that:

1. $\xi$ lies on the border (rim) of $\lambda$ — every box of $\xi$ has at least one edge on the outer boundary.
2. $\xi$ contains no $2\times 2$ square of boxes.
3. The removal of $\xi$ from $\lambda$ produces a valid Young diagram $\lambda \setminus \xi$.

The height of a border strip $\xi$, denoted $\mathrm{ht}(\xi )$, is the number of rows occupied by $\xi$ minus one.

The Murnaghan-Nakayama rule. Let $\mu =({\mu }_1,{\mu }_2,\dots ,{\mu }_{\ell })⊢n$ be a cycle type of $S_n$, with parts written in any order. Then

$${\chi }^{\lambda }(\mu )=\sum _{\xi }(-1{)}^{\mathrm{ht}(\xi )}{\chi }^{\lambda \setminus \xi }(\mu \setminus {\mu }_1)$$

where the sum runs over all border strips $\xi$ of length ${\mu }_1$ in $\lambda$, and $\mu \setminus {\mu }_1=({\mu }_2,{\mu }_3,\dots ,{\mu }_{\ell })$.

The base case is ${\chi }^{(1)}()=1$ (the character of the unit representation of $S_1$ on the empty cycle type).

Counterexamples to common slips

• A border strip is not the same as a skew shape. A skew shape $\lambda /\mu$ can have disconnected components, but a border strip must be connected.

• The height is rows minus one, not the number of boxes. A strip of length $5$ occupying $3$ rows has height $2$, not $5$.

• The order of the parts of $\mu$ does not matter. The rule gives the same answer regardless of which part ${\mu }_i$ is removed first, but the intermediate diagrams differ.

Key theorem with proof [Intermediate+]

Theorem (Murnaghan-Nakayama rule). For $\lambda ⊢n$ and $\mu ⊢n$,

$${\chi }^{\lambda }({\mu }_1,{\mu }_2,\dots ,{\mu }_{\ell })=\sum _{\xi }(-1{)}^{\mathrm{ht}(\xi )}{\chi }^{\lambda \setminus \xi }({\mu }_2,\dots ,{\mu }_{\ell })$$

where the sum is over all border strips $\xi$ of length ${\mu }_1$ in $\lambda$.

Proof. The proof proceeds by induction on $n$, using the branching rule for restricting $S_n$-representations to $S_{n-1}$.

Step 1: The branching rule. For $\lambda ⊢n$, the restriction of $V^{\lambda }$ from $S_n$ to $S_{n-1}$ decomposes as

$${\mathrm{Res}}_{S_{n-1}}^{S_n}{V}^{\lambda }=\underset{{\lambda }^{-}}{⨁}{V}^{{\lambda }^{-}}$$

where ${\lambda }^{-}$ ranges over all partitions obtained by removing a single corner box from $\lambda$. (A corner box is a box whose removal leaves a valid Young diagram.)

Step 2: Iterated restriction. Restrict from $S_n$ to $S_{n-{\mu }_1}$ by removing ${\mu }_1$ boxes one at a time. Each step removes one corner box, and the branching rule tracks which diagrams survive. After ${\mu }_1$ steps, the surviving diagrams are precisely those obtained by removing a connected border strip of ${\mu }_1$ boxes from $\lambda$.

Step 3: The sign. Each border-strip removal corresponds to a sequence of ${\mu }_1$ single-box removals. When consecutive removals occur in the same row, the branching rule contributes no sign. When a removal moves to a new row (descending), the character acquires a factor of $-1$. The total number of row transitions is $\mathrm{ht}(\xi )$, so the accumulated sign is $(-1{)}^{\mathrm{ht}(\xi )}$.

Step 4: The ${\mu }_1$-cycle contribution. A permutation $\sigma$ of cycle type $({\mu }_1,{\mu }_2,\dots )$ can be written as $\sigma =\tau \cdot c$ where $c$ is a ${\mu }_1$-cycle and $\tau$ has cycle type $({\mu }_2,\dots ,{\mu }_{\ell })$ in $S_{n-{\mu }_1}$. The character ${\chi }^{\lambda }(\sigma )$ factors through the restriction to $S_{n-{\mu }_1}$ by applying the branching rule ${\mu }_1$ times. Each border strip $\xi$ of length ${\mu }_1$ produces one summand with sign $(-1{)}^{\mathrm{ht}(\xi )}$, and the remaining character is evaluated on $\tau$, which has cycle type $({\mu }_2,\dots ,{\mu }_{\ell })$ in $S_{n-{\mu }_1}$.

Combining: ${\chi }^{\lambda }(\mu )={\sum }_{\xi }(-1{)}^{\mathrm{ht}(\xi )}{\chi }^{\lambda \setminus \xi }(\mu \setminus {\mu }_1)$.

The base case $\lambda =(1)$ gives ${\chi }^{(1)}()=1$ (the character of the unit representation on the identity conjugacy class), completing the induction. $\square$

Bridge. The foundational reason the Murnaghan-Nakayama rule works is that the branching rule decomposes the restriction ${\mathrm{Res}}_{S_{n-1}}^{S_n}$ by removing single corner boxes, and this is exactly the one-step version of the border-strip removal. The central insight is that iterated branching for ${\mu }_1$ steps produces a sum over all ways to remove a connected strip of ${\mu }_1$ boxes, with the sign accumulating from row transitions. This result builds toward the Frobenius character formula 07.05.01 which computes the same characters via symmetric functions, and appears again in the Littlewood-Richardson rule where border-strip removals compute structure constants for the representation ring. Putting these together, the bridge is between the combinatorial picture (removing strips from diagrams) and the algebraic picture (evaluating characters on conjugacy classes), and the pattern recurs in the modular representation theory of $S_n$ where Nakayama's conjecture (now theorem) uses the same border-strip data to classify blocks.

Exercises [Intermediate+]

Advanced results [Master]

Theorem 1 (The Frobenius character formula as a corollary). The Frobenius formula ${\chi }^{\lambda }(\mu )=[x^{\lambda +\delta }]p_{\mu }\cdot \Delta$ is equivalent to the MN rule. The border-strip expansion of the MN rule is the recursive extraction of the power-sum factors $p_{{\mu }_i}$ from the Vandermonde $\Delta$. Sagan The Symmetric Group §4.4 gives the explicit equivalence ^{[Sagan — The Symmetric Group]}.

Theorem 2 (Nakayama's block description). In the modular representation theory of $S_n$ over a field of characteristic $p$, two irreducible representations $V^{\lambda }$ and $V^{\mu }$ lie in the same block if and only if $\lambda$ and $\mu$ have the same $p$-core — the diagram obtained by removing all border strips of length $p$ from each. Nakayama 1940 ^{[Nakayama 1940 — On some modular properties]} proved this classification, which is the bridge from ordinary to modular character theory for $S_n$.

Theorem 3 (The Littlewood-Richardson rule and border strips). The Littlewood-Richardson coefficient $c_{\mu \nu }^{\lambda }$ (the multiplicity of $V^{\lambda }$ in $V^{\mu }\otimes V^{\nu }$) can be computed by a skew-tableau counting rule that generalises the MN strip-removal procedure. The border strips in the MN rule are the building blocks of the LR skew shapes.

Theorem 4 (Height-generating function). Define $h(\lambda ,k)={\sum }_{\xi }(-1{)}^{\mathrm{ht}(\xi )}$ where the sum is over all border strips of length $k$ in $\lambda$. Then $h(\lambda ,k)$ is the coefficient of $t^k$ in the product ${\prod }_{(i,j)\in \lambda }(1-t^{h_{ij}}{)}^{-1}$ where $h_{ij}$ is the hook length at cell $(i,j)$. This connects the signed strip count to the hook-length formula.

Theorem 5 (The MN rule as a symmetric-function identity). In the ring of symmetric functions, the MN rule expresses the expansion of the Schur function $s_{\lambda }$ in the power-sum basis $\{p_{\mu }\}$:

$$s_{\lambda }=\sum _{\mu ⊢|\lambda |}\frac{{\chi }^{\lambda }(\mu )}{z_{\mu }}{p}_{\mu }$$

where $z_{\mu }={\prod }_i{i}^{m_i}{m}_i!$ and $m_i$ is the multiplicity of $i$ in $\mu$. The MN rule computes ${\chi }^{\lambda }(\mu )$ recursively, giving a combinatorial algorithm for this expansion.

Synthesis. The foundational reason the Murnaghan-Nakayama rule is so powerful is that it replaces algebraic character computations with diagrammatic strip removals, and this is exactly the bridge between the representation theory of $S_n$ and the combinatorics of Young diagrams. The central insight is that the branching rule — removing one corner box at a time — iterated ${\mu }_i$ times produces border strips, with the sign $(-1{)}^{\mathrm{ht}(\xi )}$ accumulating from row transitions. Putting these together, the MN rule computes any character value ${\chi }^{\lambda }(\mu )$ as a signed sum over diagrammatic paths, each path being a sequence of strip removals. The pattern generalises to the Frobenius character formula (where the same computation appears as a coefficient extraction from $p_{\mu }\cdot \Delta$), appears again in Nakayama's block classification (where $p$-cores determine the block structure in modular representation theory), and identifies the character ring of $S_n$ with the ring of symmetric functions via the characteristic map. The bridge is that the combinatorial data of border strips — their lengths, heights, and signed contributions — encodes the full character theory of the symmetric group.

Full proof set [Master]

Proposition 1 (Branching rule for $S_n\downarrow S_{n-1}$). For $\lambda ⊢n$,

$${\mathrm{Res}}_{S_{n-1}}^{S_n}{V}^{\lambda }=\underset{{\lambda }^{-}}{⨁}{V}^{{\lambda }^{-}}$$

where ${\lambda }^{-}$ ranges over partitions of $n-1$ obtained by removing one corner box from $\lambda$.

Proof. By the Frobenius reciprocity theorem, the multiplicity of $V^{{\lambda }^{-}}$ in ${\mathrm{Res}}_{S_{n-1}}^{S_n}{V}^{\lambda }$ equals the multiplicity of $V^{\lambda }$ in ${\mathrm{Ind}}_{S_{n-1}}^{S_n}{V}^{{\lambda }^{-}}$. The Young diagram of ${\lambda }^{-}$ is obtained by adding one box to ${\lambda }^{-}$, and the possible additions are precisely the boxes that can be added to ${\lambda }^{-}$ to produce a valid Young diagram. These are in bijection with the corner boxes of $\lambda$. By Pieri's rule (or the branching rule for tableaux), each such addition contributes multiplicity $1$. So the restriction decomposes with multiplicity $1$ for each ${\lambda }^{-}$ obtained by removing a corner box, and multiplicity $0$ otherwise. $\square$

Proposition 2 (Border strips from iterated branching). Removing ${\mu }_1$ boxes from $\lambda$ one at a time via the branching rule produces exactly the border strips of length ${\mu }_1$ in $\lambda$.

Proof. Each single-box removal removes a corner. A sequence of ${\mu }_1$ corner removals traces a connected path along the rim of the diagram. For the sequence to produce valid Young diagrams at every step, each successive removal must be a corner of the current diagram. This forces the ${\mu }_1$ removed boxes to form a connected set along the border with no $2\times 2$ square (a $2\times 2$ square would require two boxes in the same step to be corners, which is impossible). Hence the set of removed boxes is a border strip. Conversely, every border strip can be removed by peeling off one corner box at a time from the strip, starting from one end. $\square$

Connections [Master]

• Symmetric group representation 07.05.01. The MN rule computes the irreducible characters ${\chi }^{\lambda }$ of $S_n$ whose existence and classification are established in that unit. The Frobenius-Young bijection between partitions and irreducibles is the foundation on which the MN rule builds, and the hook-length formula from that unit is complementary to the MN rule: one computes dimensions, the other computes character values.

• Young diagram 07.05.02. The entire mechanics of the MN rule operates on Young diagrams: border strips, rim hooks, heights, and diagram removals. The Young diagram is the computational canvas on which the rule draws, and its combinatorial properties (corners, borders, rim) are the data the rule consumes.

• Specht module 07.05.03. The MN rule computes the characters of the Specht modules $S^{\lambda }$ over fields of characteristic zero. In positive characteristic, the same border-strip data determines the block structure via Nakayama's conjecture, connecting the ordinary character theory computed by the MN rule to the modular decomposition of Specht modules.

Historical & philosophical context [Master]

Murnaghan 1937, in On the representations of the symmetric group ^{[Murnaghan1937]}, discovered the recursive character formula by extracting coefficients from the Frobenius determinantal formula. Murnaghan observed that the character ${\chi }^{\lambda }(\mu )$ could be computed by a single recursive step: remove a border strip of length ${\mu }_1$ from $\lambda$ and recurse on the smaller diagram, with a sign determined by the geometry of the strip.

Nakayama 1940, in On some modular properties of irreducible representations of a symmetric group ^{[Nakayama1940]}, gave the full combinatorial formulation using border strips (which he called rim hooks) and proved the recursive rule from the branching theorem. Nakayama's deeper contribution was the conjecture — now the Nakayama conjecture, proved by Brauer and Robinson 1947 — that the block structure of $S_n$ in characteristic $p$ is determined by $p$-cores. The modern exposition of the MN rule, with the clean combinatorial proof via iterated branching, appears in Sagan The Symmetric Group §4 and Stanley Enumerative Combinatorics Vol. II §7.

Bibliography [Master]

@article{Murnaghan1937,
  author = {Murnaghan, Francis D.},
  title = {On the representations of the symmetric group},
  journal = {American Journal of Mathematics},
  volume = {59},
  year = {1937},
  pages = {437--488},
}

@article{Nakayama1940a,
  author = {Nakayama, Tadasi},
  title = {On some modular properties of irreducible representations of a symmetric group, I},
  journal = {Japanese Journal of Mathematics},
  volume = {17},
  year = {1940},
  pages = {89--108},
}

@article{Nakayama1940b,
  author = {Nakayama, Tadasi},
  title = {On some modular properties of irreducible representations of a symmetric group, II},
  journal = {Annals of Mathematics},
  volume = {41},
  year = {1940},
  pages = {733--746},
}

@book{Sagan2001,
  author = {Sagan, Bruce E.},
  title = {The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions},
  publisher = {Springer},
  year = {2001},
  edition = {2nd},
}

@book{Stanley1999,
  author = {Stanley, Richard P.},
  title = {Enumerative Combinatorics, Volume 2},
  publisher = {Cambridge University Press},
  year = {1999},
}