Combinatorial Representation Theory

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 17 September 2013

Appendix A

A2. Partitions and tableaux

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} \\ \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} 0 1 2 3 4 -1 0 1 2 3 -2 -1 0 1 -3 -2 -4 -3 -5 -4 -6 -7 & 12 9 5 4 2 11 8 4 3 1 9 6 2 1 6 3 5 2 4 1 2 1 \\ \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} \\ \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. $$1 2 5 9 13 3 6 10 14 16 4 8 15 17 7 12 11 20 18 21 19 22$$ 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{’s}$ in $T\text{.}$ $$\begin{array}{c} 1 1 1 2 3 2 2 4 4 5 3 3 5 5 6 7 7 8 8 9 10 11 \\ \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} 1 1 1 2 2 3 4 3 4 5 6 7 8 & 1 1 1 2 2 3 3 4 5 5 6 7 8 \\ 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} \\ \begin{array}{ccc}\lambda /\mu & =& \left(86333\right)/\left(5222\right)\\ \text{wt}(\lambda /\mu )& =& {(-1)}^{5-1}\end{array}\end{array}$$

Let $\lambda$ and $\mu =({\mu }_1,\dots ,{\mu }_{\ell })$ be partitions of $n\text{.}$ A $\mu \text{-border}$ strip tableau of shape $\lambda$ is a sequence of partitions $$T=(\varnothing ={\lambda }^{\left(0\right)}\subseteq {\lambda }^{\left(1\right)}\subseteq \cdots \supseteq {\lambda }^{(\ell -1)}\subseteq {\lambda }^{\left(\ell \right)}=\lambda )$$ such that, for each $1\le i\le \ell ,$

(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.

Notes and references

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..

page history