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

[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

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.

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

For weak compositions, the number is , since each k-composition of n+k corresponds to a weak one of n by the rule [a+b+...+c=n+k]→[(a-1)+(b-1)+...+(c-1)=n].

[edit] See also

• Composition for other meanings of Composition in mathematics
• Combinadic

[edit] External links

• Partition and composition calculator