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 deemed to be different compositions, while they would be considered to be the same partition. A composition where some of the summands are allowed to be zero is sometimes referred to as a weak composition.
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
Conventionally the empty composition is counted as the sole composition of 0, and there are no compositions of negative integers. There are 2n−1 compositions of n≥1; here is a proof: Placing either a plus sign or a comma in each of the n-1 boxes of the array
- <math>
\big(\,
\overbrace{1\, \square\, 1\, \square\, \ldots\, \square\, 1\,
\square\, 1}^n\,
\big)
</math> produces a unique composition of n. Conversely, every composition of n determines an assignment of pluses and commas. Since there are n≥1 binary choices, the result follows. <math>\square</math> A more refined argument shows that the number of compositions of n into exactly k parts is given by the binomial coefficient <math>{n-1\choose k-1}</math>. This gives an alternate proof of the above fact since
- <math> \sum_{k=0}^{n} {n \choose k} = 2^n.</math>
See also
- Composition for other meanings of Composition in mathematics
- Combinadic
