counting compositions of an integer (original) (raw)

For some small values of n, we have

In fact, it is easy to see that Cn=2⁢Cn-1 for n>1: each composition (a1,…,ak) of n-1 can be associated with two different compositions of n

We thus get a map φ:Sn-1×{0,1}→Sn given by

and this map is clearly injective. But it is also clearly surjective, for given (a1,…,ak)∈Sn, if ak=1 then the composition is the image of ((a1,…,ak-1),0) while if ak>1, then it is the image of ((a1,…,ak-1),1). This proves that (for n>1) Cn=2⁢Cn-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 (n-1k-1) ways to do this, so the number of compositions of n into k parts is simply (n-1k-1). Note that this gives even a simpler proof of the first result, since