On Sunday, September 28, 2003, at 11:10 am, Jon Perry wrote:

The number of ordered partitions of n into exactly k parts corresponds to Pascal's triangle.

The term "composition" is usually used for "ordered partition." When I've taught discrete math classes, we call this a "stars and bars" situation. The ordered partitions of 3 into 3 parts, for example, are ***|| **|*| *|**| |***| **||* *|*|* |**|* *||** |*|** ||*** 3+0+0 2+1+0 1+2+0 0+3+0 2+0+1 1+1+1 0+2+1 1+0+2 0+1+2 0+0+3 Put down three stars, and partition them into three groups by inserting two bars -- but that's the same as having five spaces and picking two to be bars. Hooray binomial coefficients: n+k-1 choose k-1 (or choose n, of course). If you want compositions of n into exactly k *nonzero* parts, just set k stars aside, and think of them as belonging to the first through nth parts, respectively. The argument above gives (n-k) + (k-1) choose k-1, which I've found works much better than memorizing the formula with the k's already cancelled, even if n-1 choose k-1 is more succinct. --Michael Kleber kleber@brandeis.edu