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}