counting compositions of an integer

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 (http://planetmath.org/PartialOrder) matters).

For some small values of $n$, we have

 $\displaystyle C_{0}$ $\displaystyle=1$ $\displaystyle C_{1}$ $\displaystyle=1$ $\displaystyle C_{2}$ $\displaystyle=2\qquad(2),(1,1)$ $\displaystyle C_{3}$ $\displaystyle=4\qquad(3),(1,2),(2,1),(1,1,1)$

In fact, it is easy to see that $C_{n}=2C_{n-1}$ for $n>1$: each composition $(a_{1},\ldots,a_{k})$ of $n-1$ can be associated with two different compositions of $n$

 $\displaystyle(a_{1},a_{2},\ldots,a_{k},1)$ $\displaystyle(a_{1},a_{2},\ldots,a_{k}+1)$

We thus get a map $\varphi:S_{n-1}\times\{0,1\}\to S_{n}$ given by

 $\displaystyle\varphi((a_{1},\ldots,a_{k}),0)=(a_{1},\ldots,a_{k},1)$ $\displaystyle\varphi((a_{1},\ldots,a_{k}),1)=(a_{1},\ldots,a_{k}+1)$

and this map is clearly injective. But it is also clearly surjective, for given $(a_{1},\ldots,a_{k})\in S_{n}$, if $a_{k}=1$ then the composition is the image of $((a_{1},\ldots,a_{k-1}),0)$ while if $a_{k}>1$, then it is the image of $((a_{1},\ldots,a_{k-1}),1)$. This proves that (for $n>1$) $C_{n}=2C_{n-1}$.

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}$
Title counting compositions of an integer CountingCompositionsOfAnInteger 2013-03-22 17:37:55 2013-03-22 17:37:55 rm50 (10146) rm50 (10146) 5 rm50 (10146) Result msc 05-00 composition