Composition (number theory)

From Wikipedia, the free encyclopedia

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.

A composition where some of the summands are allowed to be zero is sometimes referred to as a weak composition.

1 Examples
2 Number of compositions
3 See also
4 External links

[edit] 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.

[edit] Number of compositions

There are 2ⁿ⁻¹ compositions of n≥1, conventionally the empty composition is counted as the sole composition of 0, and there are no compositions of negative integers.

The number of compositions of n into exactly k parts is given by the binomial coefficient ${n-1\choose k-1}$ .