Abstract Nonsense

Crushing one theorem at a time

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} byf_{\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.

Advertisements

May 10, 2011 - Posted by | Algebra, Algebraic Combinatorics, Representation Theory | , , , , , , ,

7 Comments »

  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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: