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
Canonical name	CountingCompositionsOfAnInteger
Date of creation	2013-03-22 17:37:55
Last modified on	2013-03-22 17:37:55
Owner	rm50 (10146)
Last modified by	rm50 (10146)
Numerical id	5
Author	rm50 (10146)
Entry type	Result
Classification	msc 05-00
Defines	composition