Composition (number theory)
Encyclopedia
In mathematics
, a composition of an integer
n is a way of writing n as the sum
of a sequence of (strictly) positive integers. Two sequences that differ in the order of their terms define different compositions of their sum, while they are considered to define the same partition
of that number. Any integer has finitely many distinct compositions. Negative numbers do not have any compositions, but 0 has one composition, the empty sequence. Any positive integer n has 2n−1 distinct compositions. This is a power of two
, because every composition matches a binary number.
A weak composition of an integer n is similar to a composition of n, but allowing terms of the sequence to be zero: it is a way of writing n as the sum of a sequence of non-negative integers. As a consequence any positive integer admits infinitely many weak compositions (if their length is not bounded). Adding a number of terms 0 to the end of a weak composition is usually not considered to define a different weak composition, in other words weak compositions are assumed to be implicitly extended indefinitely by terms 0.
Compare this with the seven partitions of 5:
It is possible to put constraints on the parts of the compositions. For example the five compositions of 5 into distinct terms are:
Compare this with the three partitions of 5 into distinct terms:
There are 2n−1 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. The same argument shows that the number of compositions of n into exactly k parts is given by the binomial coefficient
. Note that by summing over all possible number of parts we recover 2n−1 as the total number of compositions of n:
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].
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a composition of an integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
n is a way of writing n as the sum
SUM
SUM can refer to:* The State University of Management* Soccer United Marketing* Society for the Establishment of Useful Manufactures* StartUp-Manager* Software User’s Manual,as from DOD-STD-2 167A, and MIL-STD-498...
of a sequence of (strictly) positive integers. Two sequences that differ in the order of their terms define different compositions of their sum, while they are considered to define the same partition
Partition (number theory)
In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a...
of that number. Any integer has finitely many distinct compositions. Negative numbers do not have any compositions, but 0 has one composition, the empty sequence. Any positive integer n has 2n−1 distinct compositions. This is a power of two
Power of two
In mathematics, a power of two means a number of the form 2n where n is an integer, i.e. the result of exponentiation with as base the number two and as exponent the integer n....
, because every composition matches a binary number.
A weak composition of an integer n is similar to a composition of n, but allowing terms of the sequence to be zero: it is a way of writing n as the sum of a sequence of non-negative integers. As a consequence any positive integer admits infinitely many weak compositions (if their length is not bounded). Adding a number of terms 0 to the end of a weak composition is usually not considered to define a different weak composition, in other words weak compositions are assumed to be implicitly extended indefinitely by terms 0.
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 2n−1 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. The same argument shows that the number of compositions of n into exactly k parts is given by the binomial coefficient
Binomial coefficient
In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the binomial coefficient indexed by n and k is usually written \tbinom nk , and it is the coefficient of the x k term in...
. Note that by summing over all possible number of parts we recover 2n−1 as the total number of compositions of n:
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].