The Unapologetic Mathematician

Mathematics for the interested outsider


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


and one possible Young tableau with this shape is


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


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


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


  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: Logo

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: