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.

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 2ⁿ⁻¹ 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

$\{(n-1)!\; \backslash over\; (k-1)!(n-k)!\}$,

See also

• Composition disambiguation page

External links

• Partition and composition calculator

Number theory