Composition (number theory)
|
|
In mathematics, a composition of a positive integer n is a way of writing n as a sum of positive integers. Two sums which differ in the order of their summands are considered to be different compositions, while they would be considered to be the same partition.
| Contents |
Examples
The sixteen compositions of 5 are:
- 5
- 4+1
- 3+2
- 3+1+1
- 2+3
- 2+2+1
- 2+1+2
- 2+1+1+1
- 1+4
- 1+3+1
- 1+2+2
- 1+2+1+1
- 1+1+3
- 1+1+2+1
- 1+1+1+2
- 1+1+1+1+1.
Compare this with the seven partitions of 5:
- 5
- 4+1
- 3+2
- 3+1+1
- 2+2+1
- 2+1+1+1
- 1+1+1+1+1.
It is possible to put constraints on the parts of the compositions. For example the five compositions of 5 into distinct terms are:
- 5
- 4+1
- 3+2
- 2+3
- 1+4.
Compare this with the three partitions of 5 into distinct terms:
- 5
- 4+1
- 3+2.
Number of compositions
There are 2n-1 compositions of n; conventionally there is one composition of 0, and no compositions of negative integers.
The number of compositions of n into exactly k parts is
- <math>{(n-1)! \over (k-1)!(n-k)!}<math>,
i.e. the combination "n-1 choose k-1".
See also
- Composition disambiguation page
External links
- Partition and composition calculator (http://www.btinternet.com/~se16/js/partitions.htm)