counting compositions of an integer
A composition of a nonnegative integer n is a sequence
(a1,…,ak) of positive integers with ∑ai=n. Denote by Cn the number of compositions of n, and denote by Sn 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
C0 | =1 | ||
C1 | =1 | ||
C2 | =2 | ||
In fact, it is easy to see that for : each composition of can be associated with two different compositions of
We thus get a map given by
and this map is clearly injective. But it is also clearly surjective
, for given , if then the composition is the image of while if , then it is the image of . This proves that (for ) .
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 ways to do this, so the number of compositions of into parts is simply . Note that this gives even a simpler proof of the first result, since
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 |