# Abstract Nonsense

## Partitions, Ferrer’s Diagrams, and Young Tableaux

Point of Post: In this post we discuss the notion of  partitions, Ferrer’s diagrams, and Young Tableaux (and their standard type).

$\text{ }$

Motivation

There is beautiful interplay between algebra and combinatorics which can be seen in the representation theory of the symmetric group. At the center of this correspondence is the notion of a Ferrer’s diagram and a Young tableau which, as we shall see, will serve to ‘index’ in a very fruitful way the representations of $S_n$. This really is one of the most beautiful parts of basic finite group representation theory.

$\text{ }$

Paritions

$\text{ }$

Let $n$ be a natural number, we say that the $r$-tuple $\lambda=(\lambda_1,\cdots,\lambda_r)$ is a partition of $n$, denoted $\lambda\vdash n$, if $\lambda_1\geqslant\cdots\geqslant \lambda_r$ and $\lambda_1+\cdots+\lambda_r=n$. The number of partitions of $n$ is denoted by $p(n)$ which is called the partition function. Clearly the partition function represent many combinatorial situations such as the number of unordered (order doesn’t matter) ways to write $n$ as the sum of natural numbers, the number of ways to partition a set of $n$-indistinguishable objects, etc. To us the most important interpretation is as follows:

$\text{ }$

Theorem: The number of conjugacy classes of the symmetric group $S_n$ is equal to $p(n)$.

Proof: It is clear from our classification of conjugacy classes in $S_n$ that the number of conjugacy classes is equal to the number of different cycle types of permutations of $\pi$. That said, clearly the number of different cycle types is equal to the number of ways one can partition with parentheses the following array of bullets (where the bullets represent arbitrary elements of $[n]$)

$\text{ }$

$\bullet\bullet\cdots\bullet$

$\text{ }$

but by previous observation (since this is the number of ways to partition a set of $n$ indistinguishable objects) this is equal to $p(n)$. $\blacksquare$

$\text{ }$

Ferrer’s Diagrams

$\text{ }$

There is another combinatorial object which is closely related to partitions. Namely, a Ferrer’s diagram on $n$-boxes $\mathcal{F}$also called an $n$-frame is a collection of $n$ left-justified boxes arranged in rows where the number of boxes in a given row is less than or equal the number of boxes in the row above it. For example,

$\text{ }$

$\begin{array}{|c|c|c|}\cline{1-3}\hphantom{1} &\hphantom{1} &\hphantom{1}\\ \cline{1-3}&&\\ \cline{1-3}&&\multicolumn{1}{c}{}\\ \cline{1-2}&\multicolumn{2}{c}{}\\ \cline{1-1}\end{array}$

$\text{ }$

We can specify an $n$-frame by its row structure $(m_1,\cdots,m_r)$ where $r$ is the number of rows and $m_j$ the number of boxes in the $j^{\text{th}}$ row. So, for example the $9$-frame above could be denoted $(3,3,2,1)$. Since $m_1\geqslant\cdots\geqslant m_r$ and $m_1+\cdots+m_r$ we obviously have a bijection between the number of $n$-frames and the number of partitions of $n$. Thus, by the previous section we have that the number $p(n)$ of $n$-frames is equal to the number of conjugacy classes of $S_n$.

$\text{ }$

Young Tableaux and Standard Young Tableaux

$\text{ }$

A Young tableau on $n$-boxes $\mathcal{T}$ or simply a $n$-tableau is an $n$-frame $\mathcal{F}$ along with a (bijective) filling in of the $n$-frame’s boxes with all the elements of $[n]$. So, for example a $n$-tableau whose frame is the above $n$-frame would be

$\text{ }$

$\begin{array}{|c|c|c|}\cline{1-3}9&1&4\\ \cline{1-3}5&6&2\\ \cline{1-3}8&3&\multicolumn{1}{c}{}\\ \cline{1-2}7&\multicolumn{2}{c}{}\\ \cline{1-1}\end{array}$

$\text{ }$

We denote the frame of a tableau $\mathcal{T}$ by $\text{Frame}(\mathcal{T})$. It’s evident that the number of tableau $\mathcal{T}$ such that $\text{Frame}(\mathcal{T})=\mathcal{F}$ for a given $n$-frame $\mathcal{F}$ is equal to $n!$.

$\text{ }$

More useful to us though is the notion of a standard Young tableau. Namely, a standard Young tableau on $n$-boxes $\mathcal{T}$, or simply a standard $n$-tableau is a $n$-tableau $\mathcal{T}$ such that rows and columns are increasing. So, while the above $9$-tableau is not standard the $9$-tableau

$\text{ }$

$\begin{array}{|c|c|c|}\cline{1-3}1&3&5\\ \cline{1-3}2&4&9\\ \cline{1-3}6&7&\multicolumn{1}{c}{}\\ \cline{1-2}8&\multicolumn{2}{c}{}\\ \cline{1-1}\end{array}$

$\text{ }$

is. For a given frame $\mathcal{F}$ we denote the number of standard young tableau $\mathcal{T}$ with $\text{Frame}(\mathcal{T})=\mathcal{F}$ by$f_{\text{st}}\left(\mathcal{F}\right)$.

$\text{ }$

$\text{ }$

References:

1. Simon, Barry. Representations of Finite and Compact Groups. Providence, RI: American Mathematical Society, 1996. Print.

May 10, 2011 -

1. […] clear that in our definition of -frames that sitting inside each -frame is a lot of -frames which can be gotten simply by […]

Pingback by Subordinate and Superordinate Frames « Abstract Nonsense | May 11, 2011 | Reply

2. […] was stated in our last post we can find a very interesting way to calculate the number, , of standard Young tableaux  with . In this post we actually prove this claim. The intuitive idea is clear, by construction of […]

Pingback by Relation Between the Number of Standard Young Tableaux on a Frame and the Number of Young Tableaux on the Frame’s Subordinate/Superordinate Frames « Abstract Nonsense | May 11, 2011 | Reply

3. […] show that there is a map . But, the fact that there exists a correspondence is obvious since we know that . What is interesting is that we are able to correspond an element an element of in a […]

Pingback by The Fundamental Result for Tableaux Combinatorics « Abstract Nonsense | May 12, 2011 | Reply

4. […] our last post we let slip the deal with looking at the combinatorial objects we have been looking at. In particular, we noted that we will associate to each -frame an irrep of . What we mentioned […]

Pingback by Hook-length in a Ferrer’s Diagram « Abstract Nonsense | May 12, 2011 | Reply

5. […] Let ( is not fixed)  be a -frame and, as usual, the number of standard Young tableaux  with . […]

Pingback by The Hook-length Formula « Abstract Nonsense | May 14, 2011 | Reply

6. […] that for a given -frame  we defined to be the set of all Young tableaux  with . What we first notice is that there is a […]

Pingback by Row and Column Stabilizer « Abstract Nonsense | May 20, 2011 | Reply

7. […] now define the condition we stated above. In particular, let be two – tableaux. We say that if there exists such that are in the same row of and the same column of . For […]

Pingback by A Weird Condition on Tableaux « Abstract Nonsense | May 22, 2011 | Reply