PlanetMath: counting compositions of an integer

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (211)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (36)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

counting compositions of an integer

(Result)

A composition of a nonnegative integer is a sequence $(a_1,\ldots,a_k)$ of positive integers with $\sum a_i=n$ . Denote by the number of compositions of , and denote by 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 , 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

: each composition $(a_1,\ldots,a_k)$ of

can be associated with two different compositions of

$\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

then the composition is the image of $((a_1,\ldots,a_{k-1}),0)$ while if

, then it is the image of $((a_1,\ldots,a_{k-1}),1)$ . This proves that (for

) $C_n = 2C_{n-1}$ .

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