Last update: 17 September 2013

*Partitions*

A *partition* is a sequence $\lambda =({\lambda}_{1},\dots ,{\lambda}_{n})$
of integers such that ${\lambda}_{1}\ge \cdots \ge {\lambda}_{n}\ge 0\text{.}$
It is conventional to identify a partition with its Ferrers diagram which has ${\lambda}_{i}$ boxes in the
$i\text{th}$ row. For example the partition $\lambda =\left(55422211\right)$
has Ferrers diagram
$$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\\ \lambda =\left(55422211\right)\end{array}$$
We number the rows and columns of the Ferrers diagram as is conventionally done for matrices. If $x$ is a box in $\lambda $
then the *content* and the *hook length* of $x$ are respectively given by
$$\begin{array}{cc}c\left(x\right)=j-i,& \text{if}\hspace{0.17em}x\hspace{0.17em}\text{is in position}\hspace{0.17em}(i,j)\in \lambda \text{, and}\\ {h}_{x}={\lambda}_{i}-i+{\lambda}_{j}^{\prime}-j+1,& \text{where}\hspace{0.17em}{\lambda}_{j}^{\prime}\hspace{0.17em}\text{is the length of the}\hspace{0.17em}j\text{th column of}\hspace{0.17em}\lambda \text{.}\end{array}$$
$$\begin{array}{cc}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n0\n1\n2\n3\n4\n\n\n\n\n-1\n0\n1\n2\n3\n\n\n\n\n-2\n-1\n0\n1\n\n\n\n\n-3\n-2\n\n\n\n\n-4\n-3\n\n\n\n\n-5\n-4\n\n\n\n\n-6\n\n\n\n\n-7\n\n\n\n& \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n12\n9\n5\n4\n2\n\n\n\n\n11\n8\n4\n3\n1\n\n\n\n\n9\n6\n2\n1\n\n\n\n\n6\n3\n\n\n\n\n5\n2\n\n\n\n\n4\n1\n\n\n\n\n2\n\n\n\n\n1\n\n\n\n\\ \text{Contents of the boxes}& \text{Hook lengths of the boxes}\end{array}$$

If $\mu $ and $\lambda $ are partitions such that the Ferrers diagram of $\mu $ is contained in the
Ferrers diagram of $\lambda $ then we write $\mu \subseteq \lambda $ and we denote the difference of the
Ferrers diagrams by $\lambda /\mu \text{.}$ We refer to $\lambda /\mu $
as a *shape* or, more specifically, a *skew shape*.
$$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\\ \lambda /\mu =\left(55422211\right)/\left(32211\right)\end{array}$$

*Tableaux*

Suppose that $\lambda $ has $k$ boxes. A *standard tableau* of shape $\lambda $ is a filling of
the Ferrers diagram of $\lambda $ with $1,2,\dots ,k$
such that the rows and columns are increasing from left to right and from top to bottom respectively.
$$\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n1\n2\n5\n9\n13\n\n\n\n\n3\n6\n10\n14\n16\n\n\n\n\n4\n8\n15\n17\n\n\n\n\n7\n12\n\n\n\n\n11\n20\n\n\n\n\n18\n21\n\n\n\n\n19\n\n\n\n\n22\n\n\n\n$$
Let $\lambda /\mu $ be a shape. A *column strict tableau* of shape $\lambda /\mu $
filled with $1,2,\dots ,n$
is a filling of the Ferrers diagram of $\lambda /\mu $ with elements of the set
$\{1,2,\dots ,n\}$ such that the rows are weakly increasing
from left to right and the columns are strictly increasing from top to bottom. The *weight* of a column strict tableau $T$
is the sequence of positive integers $\nu =({\nu}_{1},\dots ,{\nu}_{n}),$
where ${\nu}_{i}$ is the number of $i\text{\u2019s}$ in $T\text{.}$
$$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n1\n1\n1\n2\n3\n\n\n\n\n2\n2\n4\n4\n5\n\n\n\n\n3\n3\n5\n5\n\n\n\n\n6\n7\n\n\n\n\n7\n8\n\n\n\n\n8\n9\n\n\n\n\n10\n\n\n\n\n11\n\n\n\n\\ \text{Shape}\hspace{0.17em}\lambda =\left(55422211\right)\\ \text{Weight}\hspace{0.17em}\nu =\left(33323122111\right)\end{array}$$
The *word* of a column strict tableau $T$ is the sequence $w={w}_{1}{w}_{2}\cdots {w}_{p}$
obtained by reading the entries of $T$ from right to left in successive rows, starting with the top row. A word
$w={w}_{1}\cdots {w}_{p}$ is a lattice permutation if for each
$1\le r\le p$ and each $1\le i\le n-1$
the number of occurrences of the symbol $i$ in ${w}_{1}\cdots {w}_{r}$
is not less than the number of occurences of $i+1$ in ${w}_{1}\cdots {w}_{r}\text{.}$
$$\begin{array}{cc}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n1\n1\n\n\n\n\n1\n2\n2\n\n\n\n\n3\n4\n\n\n\n\n3\n\n\n\n\n4\n\n\n\n\n5\n6\n\n\n\n\n7\n\n\n\n\n8\n\n\n\n& \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n1\n1\n\n\n\n\n1\n2\n2\n\n\n\n\n3\n3\n\n\n\n\n4\n\n\n\n\n5\n\n\n\n\n5\n6\n\n\n\n\n7\n\n\n\n\n8\n\n\n\n\\ w=1122143346578& w=1122133456578\\ \text{Not a lattice permutation}& \text{Lattice permutation}\end{array}$$
A *border strip* is a skew shape $\lambda /\mu $ which is

(a) | connected (two boxes are connected if they share an edge), and |

(b) |
does not contain a $2\times 2$ block of boxes.
The weight of a border strip $\lambda /\mu $ is given by $$\text{wt}(\lambda /\mu )={(-1)}^{r(\lambda /\mu )-1},$$ where $r(\lambda /\mu )$ is the number of rows in $\lambda /\mu \text{.}$ $$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\\ \begin{array}{ccc}\lambda /\mu & =& \left(86333\right)/\left(5222\right)\\ \text{wt}(\lambda /\mu )& =& {(-1)}^{5-1}\end{array}\end{array}$$ |

(a) | ${\lambda}^{\left(i\right)}/{\lambda}^{(i-1)}$ is a border strip, and |

(b) | $|{\lambda}^{\left(i\right)}/{\lambda}^{(i-1)}|={\mu}_{i}\text{.}$ |

The weight of a $\mu \text{-border}$ strip tableau $T$ of shape $\lambda $ is $$\begin{array}{cc}\text{wt}\left(T\right)=\prod _{i=1}^{\ell -1}\text{wt}({\lambda}^{\left(i\right)}/{\lambda}^{(i-1)})\text{.}& \text{(}A\text{2.1)}\end{array}$$

**Theorem A2.2.**
*
(Murnaghan-Nakayama rule) Let $\lambda $ and $\mu $ be partitions of $n$ and let
${\chi}^{\lambda}\left(\mu \right)$ denote the irreducible character of the
symmetric group ${S}_{n}$ indexed by $\lambda $ evaluated at a permutation of cycle type
$\mu \text{.}$ Then
$${\chi}^{\lambda}\left(\mu \right)=\sum _{T}\text{wt}\left(T\right),$$
where the sum is over all $\mu \text{-border}$ strip tableaux $T$ of shape
$\lambda $ and $\text{wt}\left(T\right)$ is as given in (A2.1).
*

**References**

All of the above facts can be found in [Mac1995] Chapt. I. The proof of theorem (A2.2) is given in [Mac1995] Ch. I §7, Ex. 5.

This is the survey paper *Combinatorial Representation Theory*, written by Hélène Barcelo and Arun Ram.

*Key words and phrases.* Algebraic combinatorics, representations.

Barcelo was supported in part by National Science Foundation grant DMS-9510655.

Ram was supported in part by National Science Foundation grant DMS-9622985.

This paper was written while both authors were in residence at MSRI. We are grateful for the hospitality and financial support of MSRI..