The Unapologetic Mathematician

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.