A composition of a nonnegative integer $n$ is a sequence $(a_1,\ldots,a_k)$ of positive integers with $\sum a_i=n$ . Denote by $C_n$ the number of compositions of $n$ , and denote by $S_n$ the set of those compositions. (Note that this is a very different - and simpler - concept than the number of partitions of an integer; here the order matters).

For some small values of $n$ , we have

We can also figure out how many compositions there are of $n$ with $k$ parts. Think of a box with $n$ sections in it, with dividers between each pair of sections and a chip in each section; there are thus $n$ chips and $n-1$ dividers. If we leave $k-1$ of the dividers in place, the result is a composition of $n$ with $k$ parts; there are obviously $\dbinom{n-1}{k-1}$ ways to do this, so the number of compositions of $n$ into $k$ parts is simply $\dbinom{n-1}{k-1}$ . Note that this gives even a simpler proof of the first result, since$$\sum_{k=1}^n\dbinom{n-1}{k-1} = \sum_{k=0}^{n-1}\dbinom{n-1}{k}=2^{n-1$$