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 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.

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

Conventionally the empty composition is counted as the sole composition of 0, and there are no compositions of negative integers. There are 2ⁿ⁻¹ 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

$\big(\, \overbrace{1\, \square\, 1\, \square\, \ldots\, \square\, 1\, \square\, 1}^n\, \big)$

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. $\square$

A more refined argument shows that the number of compositions of n into exactly k parts is given by the binomial coefficient ${n-1\choose k-1}$ . This gives an alternate proof of the above fact since