The Unapologetic Mathematician

Mathematics for the interested outsider

Compositions

A “composition” is sort of like a partition, except the parts are allowed to come in any specified order. That is, a composition of n is an ordered sequence of nonnegative integers \lambda=(\lambda_1,\dots,\lambda_k) that sums up to n. Every partition is a composition — specifically one in which the sequence is nonincreasing. Since a general composition allows its parts to increase, it’s possible that some of the \lambda_i are zero, which can’t really happen for partitions.

The notions of Ferrers diagrams and Young tableaux, and Young tabloids carry over right away to compositions. For instance, the Ferrers diagram of the composition (1,3,2) is

\displaystyle\begin{array}{ccc}\bullet&&\\\bullet&\bullet&\bullet\\\bullet&\bullet&\end{array}

and one possible Young tableau with this shape is

\displaystyle\begin{array}{ccc}1&&\\2&3&4\\5&6&\end{array}

Now, it should be made clear that this is not a standard tableau, despite the fact that the rows and columns increase. The usual line is that we imagine the tableau to be at the upper-left corner of a quarter-plane, so there are cells extending out to the right and bottom of the diagram that aren’t part of the tableau. These, we say, are all filled with \infty, and so the second column of this particular tableau is “actually” (\infty,3,6,\dots), so it doesn’t actually increase after all. But as far as I can tell this is a lot of word salad designed to back up the definition we really want: the notion of standard Young tableaux only applies to partitions, not to compositions in general.

We can, however, extend the idea of the dominance order to general compositions. As usual we say that \lambda\trianglerighteq\mu if

\displaystyle\lambda_1+\dots+\lambda_i\geq\mu_1+\dots+\mu_i

for all i. We just don’t have to add up all the biggest parts first.

About these ads

January 6, 2011 - Posted by | Algebra, Representation Theory, Representations of Symmetric Groups

2 Comments »

  1. [...] letting be formed by the entries in less than or equal to . We define to be the shape of as a composition. For example, if we [...]

    Pingback by The Dominance Order on Tabloids « The Unapologetic Mathematician | January 10, 2011 | Reply

  2. [...] Any skipped or repeated numbers are fine. We say that the “content” of is the composition where is the number of entries in [...]

    Pingback by Generalized Young Tableaux « The Unapologetic Mathematician | February 2, 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

Follow

Get every new post delivered to your Inbox.

Join 391 other followers

%d bloggers like this: