|
|
|
|
counting compositions of an integer
|
(Result)
|
|
|
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 matters).
For some small values of $n$ , we have
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$
We thus get a map $\varphi:S_{n-1}\times\{0,1\}\to S_n$ given by
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$$
|
"counting compositions of an integer" is owned by rm50.
|
|
(view preamble | get metadata)
| Also defines: |
composition |
This object's parent.
|
|
Cross-references: proof, image, surjective, injective, map, easy to see, partitions, number, positive, sequence, integer
There are 55 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 2577 times total.
Classification:
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|