Composition (number theory)

In mathematics, a composition of a positive integer n is a way of writing n as a sum of positive integers. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an 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. Addition is the mathematical process of putting things together In Number theory, a partition of a positive Integer n is a way of writing n as a Sum of positive integers

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

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

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}$ . In Mathematics, the binomial coefficient \tbinom nk is the Coefficient of the x k term in the Polynomial This gives an alternate proof of the above fact since

$\sum_{k=0}^{n} {n \choose k} = 2^n.$

External links

Partition and composition calculator

Composition can refer to Composition (logical fallacy, a fallacy of ambiguation in which one assumes that a whole has a property solely because its various parts In Mathematics, a combinadic is an ordered Integer partition, or composition.

Contents

Examples

Number of compositions

See also

External links