|
|
|
|
counting compositions of an integer
|
(Result)
|
|
|
A composition of a nonnegative integer is a sequence
of positive integers with
. 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
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
|
"counting compositions of an integer" is owned by rm50.
|
|
(view preamble)
| Also defines: |
composition |
This object's parent.
|
|
Cross-references: image, surjective, injective, map, easy to see, partitions, positive, sequence, integer
There are 45 references to this entry.
This is version 2 of counting compositions of an integer, born on 2007-11-21, modified 2007-11-21.
Object id is 10053, canonical name is CountingCompositionsOfAnInteger.
Accessed 598 times total.
Classification:
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|