Rim Hooks and the Murnaghan–Nakayama Rule

Let $\lambda ⊢n$ be a partition with English Young diagram $[\lambda ]$, so that rows are numbered downward and columns rightward, and let $\nu \subseteq \lambda$ be a subpartition, so that the skew diagram $[\lambda \mathrm{/}\nu ]=[\lambda ]\setminus [\nu ]$ is the set of nodes of $[\lambda ]$ outside $[\nu ]$ (Partitions, English diagrams, and conjugation, Skew diagrams and semistandard skew tableaux). Two nodes are side-adjacent when their coordinates differ by exactly one in exactly one coordinate.

A removable border strip of $\lambda$ (also called a skew hook or rim hook) is a nonempty set $\xi$ of nodes of $[\lambda ]$ such that

(i) $\xi$ is edge-connected: any two nodes of $\xi$ are joined by a chain of side-adjacent nodes of $\xi$;

(ii) $\xi$ contains no $2\times 2$ block: there are no nodes $(i,j),(i+1,j),(i,j+1),(i+1,j+1)$ all belonging to $\xi$;

(iii) $[\lambda ]\setminus \xi$ is again the Young diagram of a partition, say $[\lambda ]\setminus \xi =[\nu ]$ for a partition $\nu ⊢n-\mathrm{\mid }\xi \mathrm{\mid }$.

Equivalently, a removable border strip is a skew diagram $\lambda \mathrm{/}\nu$ that is connected and contains no $2\times 2$ block; since the complement of $[\lambda \mathrm{/}\nu ]$ in $[\lambda ]$ is $[\nu ]$, condition (iii) is then automatic, and (i) and (ii) say exactly that the skew diagram is connected and free of $2\times 2$ blocks. We write $\xi =\lambda \mathrm{/}\nu$ in that case. The size of $\xi$ is its number of nodes $\mathrm{\mid }\xi \mathrm{\mid }$; a removable border strip of size $r$ is a removable $r$-strip, and then $\nu ⊢n-r$.

The height (also leg length) of a nonempty connected border strip $\xi$ is $\mathrm{ht}(\xi ):=(\text{number of distinct rows of }[\lambda ]\text{ occupied by }\xi )-1.$

The counting identity. If a removable border strip $\xi$ has $r$ nodes and occupies $c$ distinct columns and $w$ distinct rows of $[\lambda ]$, then $w=r-c+1$, hence $\mathrm{ht}(\xi )=r-c\ge 0$. Indeed $[\lambda \mathrm{/}\nu ]$ is a connected, $2\times 2$-free skew diagram with complement a Young diagram. Every strip node $(p,q)$ lies on the rim: if $(p+1,q+1)$ belonged to $[\lambda ]$, it could not belong to $[\nu ]$, since that would force $(p,q)\in [\nu ]$; and the partition inequalities then put all four nodes of the corresponding $2\times 2$ block in the strip, a contradiction. The rim nodes in row $p$ have columns $\max (1,{\lambda }_{p+1}),\dots ,{\lambda }_p$, where missing row lengths are zero. Read each such interval from right to left, then move down at column ${\lambda }_{p+1}$ to the next row: these are exactly the rim nodes and their side-adjacencies. Thus the rim is a single path moving left or down, and its connected subsets are subpaths. The $r-1$ steps of $\xi$ consist of $w-1$ downward steps and $c-1$ leftward steps, since the path visits exactly the $w$ occupied rows and exactly the $c$ occupied columns, whence $r-1=(w-1)+(c-1)$.

In particular $\mathrm{ht}(\xi )=0$ exactly when $\xi$ is a horizontal strip, that is, occupies at most one node in each column, and in general $c=r-\mathrm{ht}(\xi )$ is the number of columns occupied. A removable border strip of size $1$ is exactly a removable node (Removable and addable nodes): a single node is edge-connected and contains no $2\times 2$ block, and its removal leaves a Young diagram precisely when the node is removable. No choice principle is used.

• Border strips are the pieces of the rim that can be peeled off. Since $[\lambda \mathrm{/}\nu ]$ has complement the Young diagram $[\nu ]$, its nodes form a contiguous stretch of the lower-right rim of $[\lambda ]$: reading the strip from its north-east end to its south-west end one moves only leftward or downward, and the strip is determined by the pair $(\nu ,\lambda )$. This is the sense in which removable border strips are the "skew hooks" of James §18 and the "border strips" of Macdonald I §3 and §7.

• Height counts rows, not nodes in a column. A vertical strip, occupying a single column of $r$ nodes, has $c=1$ and $\mathrm{ht}=r-1$, the largest possible height for a strip of size $r$; the rows-occupied count $w=\mathrm{ht}+1=r$ then agrees with the node count. The height sign $(-1{)}^{\mathrm{ht}}$ is the one used in the Murnaghan–Nakayama rule (The Murnaghan–Nakayama character rule).

• Conventions. The empty set is not a removable border strip: condition (i) applies to a nonempty set, and the height of a strip requires at least one occupied row. A removable border strip is thus never empty, and the skew diagram $\lambda \mathrm{/}\lambda$ is valid notation for the empty diagram, but is not a removable border strip. The height convention agrees with the leg length $\mathrm{\ell }(x)$ of the hook of $x$ under the hook/rim-hook correspondence (Hooks of a partition correspond bijectively to removable border strips).

Let $\lambda ⊢n$ and $x=(i,j)\in [\lambda ]$. Let $H(x)$ be the hook of $x$, with arm length $a(x)={\lambda }_i-j$, leg length $\mathrm{\ell }(x)={\lambda }_j^{\mathrm{\prime }}-i$ and hook length $h(x)=a(x)+\mathrm{\ell }(x)+1$ (Hook, arm, leg, and hook length of a box); its two endpoints are the last node $(i,{\lambda }_i)$ of its arm and the last node $({\lambda }_j^{\mathrm{\prime }},j)$ of its leg. Let $\xi (x)$ be the unique edge-connected set of nodes of $[\lambda ]$ with endpoints $(i,{\lambda }_i)$ and $({\lambda }_j^{\mathrm{\prime }},j)$ that lies in the rim of $[\lambda ]$, i.e. consists of nodes $(p,q)$ with $(p+1,q+1)\mathrm{\notin }[\lambda ]$ (Partitions, English diagrams, and conjugation, Skew diagrams and semistandard skew tableaux). Then:

1. $\xi (x)$ is a removable border strip of $\lambda$ of size $h(x)$ and height $\mathrm{\ell }(x)$ (Removable border strips and their height), and $[\lambda ]\setminus \xi (x)$ is a Young diagram, so $\lambda \setminus \xi (x)$ is a partition of $n-h(x)$;
2. every removable border strip of $\lambda$ equals $\xi (x)$ for exactly one node $x\in [\lambda ]$; hence $x\mapsto \xi (x)$ is a bijection from the nodes of $[\lambda ]$ onto the removable border strips of $\lambda$.

Consequently the sizes of the removable border strips of $\lambda$ are exactly the hook lengths of $\lambda$, the height of $\xi (x)$ is the leg length $\mathrm{\ell }(x)$, and $x$ is removable as a node (Removable and addable nodes) if and only if $\xi (x)$ has size $1$. No choice principle is used.

• The correspondence slides the hook to the rim. The arm of the hook becomes the horizontal part of the rim subpath and the leg becomes its vertical part, which is why arm lengths and leg lengths are traded for columns and rows of the strip: the size becomes $a(x)+\mathrm{\ell }(x)+1=h(x)$ and the height becomes $\mathrm{\ell }(x)$.

• Sizes versus shapes. Hooks of different nodes can have the same length (for example $\lambda =(3,2)$ has hook lengths $4,3,1$ in its first row and $2,1$ in its second row), so the bijection is on nodes and not on sizes; what it identifies is the multiset of hook lengths of $\lambda$ with the multiset of sizes of the removable border strips of $\lambda$.

Let $R_S={⨁}_{m\ge 0}R(S_m)$ be the graded ordinary representation ring of the symmetric groups, whose multiplication is the outer induction product $\circ$ and whose unit is the trivial character of $S_0$ (The graded ordinary representation ring of the symmetric groups, The outer induction product of symmetric-group characters). For $m\ge 0$ let $[m]\in R(S_m)$ denote the trivial character of $S_m$ (so $[0]$ is the unit of $R_S$), and set $[m]:=0\in R_S$ for $m<0$; the Frobenius characteristic $\mathrm{ch}$ is the degree-preserving ring isomorphism of The Frobenius characteristic is an isometric graded ring isomorphism normed by $\mathrm{ch}({\chi }^{\nu })=s_{\nu }$ (The characteristic of a Specht character is a Schur function, The Frobenius characteristic map).

Then for every partition $\lambda =({\lambda }_1\ge \cdots \ge {\lambda }_k>0)$ of $n$, with ${\chi }^{\lambda }\in R(S_n)$ the character of the complex Specht module $S^{\lambda }$ (Column antisymmetrizers, polytabloids, and Specht modules, Complex Specht modules are irreducible), ${\chi }^{\lambda }=\det ([{\lambda }_i-i+j]{)}_{1\le i,j\le k}\text{in }{R}_S,$ where the determinant is the Leibniz expansion $\det ([{\lambda }_i-i+j])={\sum }_w\mathrm{sgn}(w)[{\lambda }_1-1+w(1)]\circ [{\lambda }_2-2+w(2)]\circ \cdots \circ [{\lambda }_k-k+w(k)]$ over the bijections $w$ of $\{1,\dots ,k\}$, with $\mathrm{sgn}$ the sign of the corresponding permutation (For $n\ge 1$, the determinant over a commutative ring by the Leibniz formula, and $\mathrm{\mid }\det A\mathrm{\mid }$ for a real matrix, Inversions, inversion number, the sign $\mathrm{sgn}(\sigma )=(-1{)}^{\mathrm{inv}(\sigma )}$, and even and odd permutations). For every such $w$ the degrees add up to ${\sum }_{i=1}^k({\lambda }_i-i+w(i))={\sum }_i{\lambda }_i=n$, so every nonzero monomial is homogeneous of degree $n$ and the determinant is a well-defined element of $R(S_n)$. For $n=0$ use $\lambda =\mathrm{\varnothing }$, $k=0$, and the empty determinant and empty product equal to $[0]$. The convention $[0]=1$ (the multiplicative identity of $R_S$) must be distinguished from the zero element $0$. No choice principle is used.

• Where the two determinant conventions enter. The entries $[{\lambda }_i-i+j]$ are zero as soon as the index ${\lambda }_i-i+j$ is negative, so very few of the $k!$ Leibniz terms survive; the terms that do survive all lie in the same degree-$n$ component. The identity ${\sum }_i({\lambda }_i-i+w(i))=n$ is the reason the determinant is an element of the homogeneous piece $R(S_n)$ rather than of the whole graded ring.

• The Jacobi–Trudi route. The proof transports the Jacobi–Trudi determinant for Schur functions through the characteristic isomorphism, which is the reason the statement is an identity in $R_S$ rather than a numerical formula: the theorem is the character-theoretic mirror of $s_{\lambda }=\det (h_{{\lambda }_i-i+j})$. James's §19 expansion of the same determinant is an independent combinatorial proof of the identical identity and is the source recorded for the statement.

Let $n\ge 1$ and let $\rho \in S_n$ be a cycle of length $n$ (for $n=1$, the identity on the sole point) (The finite symmetric group $S_n$, one-line notation, and cycle notation). Then for every partition $\lambda ⊢n$, taking ${\lambda }_2=0$ for a one-row partition, with ${\chi }^{\lambda }$ the character of the complex Specht module $S^{\lambda }$ (Column antisymmetrizers, polytabloids, and Specht modules, Virtual characters and the character ring $R(G)$ of a finite group),

${\chi }^{\lambda }(\rho )=\{\begin{array}{ll}(-1{)}^{n-x},& \lambda =(x,1^{n-x})\text{ for some }1\le x\le n,\\ 0,& \text{otherwise},\end{array}$

where $(x,1^{n-x})$ denotes the hook partition of $n$ with first part $x$. In particular ${\chi }^{(n)}(\rho )=1$ and ${\chi }^{(1^n)}(\rho )=(-1{)}^{n-1}$, and ${\chi }^{\lambda }(\rho )=0$ whenever $[\lambda ]$ contains a $2\times 2$ block of nodes, equivalently whenever ${\lambda }_2\ge 2$; in the hook case $\lambda =(x,1^{n-x})$ the numbers of rows and columns are $n-x+1$ and $x$. No choice principle is used.

• Consistency with the two extreme rows. For $x=n$ the hook is the single row $(n)$ and the value is $1$, as it must be for the trivial character; for $x=1$ it is the single column $(1^n)$ and the value is $(-1{)}^{n-1}$, the sign of an $n$-cycle, as it must be for the sign character.

• What fails for non-hooks. The value vanishes precisely when $\lambda$ contains a $2\times 2$ block, equivalently when ${\lambda }_2\ge 2$; a hook with $x\ge 2$ and $n-x\ge 1$ such as $(2,1)$ has several rows and columns and still has a nonzero value, so the vanishing criterion is the $2\times 2$ block and not the plain row-and-column count. This is the sign fact behind the Murnaghan–Nakayama rule: the first hook removal in The Murnaghan–Nakayama character rule carries the sign $(-1{)}^{\mathrm{ht}}$.

Let $r\ge 1$, $\lambda ⊢n$ and $\nu ⊢n-r$, and let $c_{\nu \mu }^{\lambda }$ be the Littlewood–Richardson coefficient, the number of Littlewood–Richardson tableaux of shape $\lambda \mathrm{/}\nu$ and content $\mu$ (Littlewood--Richardson tableaux and coefficients); thus ${\chi }^{\nu }\circ {\chi }^{\mu }={\sum }_{\lambda ⊢n}{c}_{\nu \mu }^{\lambda }{\chi }^{\lambda }$ with $\circ$ the outer induction product (The outer Littlewood–Richardson rule, The outer induction product of symmetric-group characters). If $\nu \subseteq ̸\lambda$, all coefficients below are zero by definition. Otherwise write $\lambda \mathrm{/}\nu$ as the disjoint union of its edge-connected components.

1. (LR multiplicities.) $c_{\nu ,(x,1^{r-x})}^{\lambda }=0$ for every $x$ unless $\lambda \mathrm{/}\nu$ is a union of $m\ge 1$ pairwise disjoint skew hooks with $r$ nodes in total; precisely, this means that $\lambda \mathrm{/}\nu$ contains no $2\times 2$ block, and then its $m$ edge-connected components are the skew hooks (for $m=1$, $\lambda \mathrm{/}\nu$ is a removable border strip in the sense of Removable border strips and their height). If $\lambda \mathrm{/}\nu$ is such a union occupying $c$ columns in total, then $c_{\nu ,(x,1^{r-x})}^{\lambda }=\left(\genfrac{}{}{0px}{}{m-1}{c-x}\right)(1\le x\le r),$ with the convention $\left(\genfrac{}{}{0px}{}{m-1}{c-x}\right)=0$ when $c-x<0$ or $c-x>m-1$.

2. (Alternating cancellation.) With the same convention, ${\sum }_{x=1}^r(-1{)}^{r-x}{c}_{\nu ,(x,1^{r-x})}^{\lambda }=\{\begin{array}{ll}(-1{)}^{r-c},& \lambda \mathrm{/}\nu \text{ is a connected border strip occupying }c\text{ columns},\\ 0,& \text{otherwise},\end{array}$ where "otherwise" covers both unions of $m\ge 2$ disjoint skew hooks and skew diagrams that are not unions of disjoint skew hooks. In the first case $c\ge m$, because distinct components have disjoint columns by column-convexity and each component occupies at least one column, so the terms $x=c-m+1,\dots ,c$ all occur in the range $1\le x\le r$, and the sum is ${\sum }_x(-1{)}^{r-x}\left(\genfrac{}{}{0px}{}{m-1}{c-x}\right)=(-1{)}^{r-c}{\sum }_{k=0}^{m-1}(-1{)}^k\left(\genfrac{}{}{0px}{}{m-1}{k}\right)=0$.

3. (Character form.) Since a connected border strip with $r$ nodes and $c$ columns has height $r-c$ (Removable border strips and their height), ${\sum }_{x=1}^r(-1{)}^{r-x}{\chi }^{\nu }\circ {\chi }^{(x,1^{r-x})}={\sum }_{\begin{array}{c}\lambda ⊢n\\ \lambda \mathrm{/}\nu \text{ a removable border strip of size }r\end{array}}(-1{)}^{\mathrm{ht}(\lambda \mathrm{/}\nu )}{\chi }^{\lambda },$ so every disconnected union of skew hooks cancels in the alternating hook induction of size $r$. No choice principle is used.