Recent Articles

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.

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^n-1 compostitions 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