## 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 is an ordered sequence of nonnegative integers that sums up to . 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 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 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 , and so the second column of this particular tableau is “actually” , 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 if

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

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

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