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

*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 . This really is one of the most beautiful parts of basic finite group representation theory.

*Paritions*

Let be a natural number, we say that the -tuple is a *partition *of , denoted , if and . The number of partitions of is denoted by 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 as the sum of natural numbers, the number of ways to partition a set of -indistinguishable objects, etc. To us the most important interpretation is as follows:

**Theorem: ***The number of conjugacy classes of the symmetric group is equal to .*

**Proof: **It is clear from our classification of conjugacy classes in that the number of conjugacy classes is equal to the number of different cycle types of permutations of . 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 )

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

*Ferrer’s Diagrams*

There is another combinatorial object which is closely related to partitions. Namely, a *Ferrer’s diagram on -boxes , *also called an *-frame* is a collection of 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,

We can specify an -frame by its *row structure* where is the number of rows and the number of boxes in the row. So, for example the -frame above could be denoted . Since and we obviously have a bijection between the number of -frames and the number of partitions of . Thus, by the previous section we have that the number of -frames is equal to the number of conjugacy classes of .

*Young Tableaux and Standard Young Tableaux*

A *Young tableau on -boxes* or simply a *-tableau *is an -frame along with a (bijective) filling in of the -frame’s boxes with all the elements of . So, for example a -tableau whose frame is the above -frame would be

We denote the frame of a tableau by . It’s evident that the number of tableau such that for a given -frame is equal to .

More useful to us though is the notion of a standard Young tableau. Namely, a *standard Young tableau on -boxes *, or simply a *standard -tableau* is a -tableau such that rows and columns are increasing. So, while the above -tableau is not standard the -tableau

is. For a given frame we denote the number of standard young tableau with by.

**References:**

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

[…] 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 |

[…] 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 |

[…] 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 |

[…] 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 |

[…] 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 |

[…] 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 |

[…] 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 |