Combinatorial Representation Theory

Last update: 17 September 2013

Appendix A

A2. Partitions and tableaux

Partitions

A partition is a sequence $\lambda =\left({\lambda }_{1},\dots ,{\lambda }_{n}\right)$ 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 $λ=(55422211)$ 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 $c(x)=j-i, if x is in position (i,j)∈λ, and hx=λi-i+λj′-j+1, where λj′ is the length of the jth column of λ.$ $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 Contents of the boxes Hook lengths of the boxes$

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. $λ/μ=(55422211)/(32211)$

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 $\left\{1,2,\dots ,n\right\}$ 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 =\left({\nu }_{1},\dots ,{\nu }_{n}\right),$ where ${\nu }_{i}$ is the number of $i\text{’s}$ in $T\text{.}$ $1 1 1 2 3 2 2 4 4 5 3 3 5 5 6 7 7 8 8 9 10 11 Shape λ=(55422211) Weight ν=(33323122111)$ 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{.}$ $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 Not a lattice permutation Lattice permutation$ 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×2$ block of boxes. The weight of a border strip $\lambda /\mu$ is given by $wt(λ/μ)= (-1)r(λ/μ)-1,$ where $r\left(\lambda /\mu \right)$ is the number of rows in $\lambda /\mu \text{.}$ $λ/μ = (86333)/(5222) wt(λ/μ) = (-1)5-1$
Let $\lambda$ and $\mu =\left({\mu }_{1},\dots ,{\mu }_{\ell }\right)$ be partitions of $n\text{.}$ A $\mu \text{-border}$ strip tableau of shape $\lambda$ is a sequence of partitions $T= ( ∅= λ(0)⊆ λ(1)⊆ ⋯⊇ λ(ℓ-1)⊆ λ(ℓ)=λ )$ such that, for each $1\le i\le \ell ,$
 (a) ${\lambda }^{\left(i\right)}/{\lambda }^{\left(i-1\right)}$ is a border strip, and (b) $|{\lambda }^{\left(i\right)}/{\lambda }^{\left(i-1\right)}|={\mu }_{i}\text{.}$

The weight of a $\mu \text{-border}$ strip tableau $T$ of shape $\lambda$ is $wt(T)= ∏i=1ℓ-1 wt(λ(i)/λ(i-1)). (A2.1)$

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 $χλ(μ)= ∑Twt(T),$ 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..