Composition (combinatorics)

In mathematics, a composition of an integer n is a way of writing n as the sum of a sequence of 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 integer partition of that number. Every integer has finitely many distinct compositions. Negative numbers do not have any compositions, but 0 has one composition, the empty sequence. Each positive integer n has 2 n−1 distinct compositions. between 3 bit binary numbers and compositions of 4 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 every 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. To further generalize, an A-restricted composition of an integer n, for a subset A of the (nonnegative or positive) integers, is an ordered collection of one or more elements in A whose sum is n.

In mathematics, a composition of an integer n is a way of writing n as the sum of a sequence of 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 integer partition of that number. Every integer has finitely many distinct compositions. Negative numbers do not have any compositions, but 0 has one composition, the empty sequence. Each positive integer n has 2 n−1 distinct compositions. between 3 bit binary numbers and compositions of 4 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 every 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. To further generalize, an A-restricted composition of an integer n, for a subset A of the (nonnegative or positive) integers, is an ordered collection of one or more elements in A whose sum is n.

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.

Number of compositions

to count the {1, 2}-restricted compositions of n, the number of ways one can ascend a staircase of length n, taking one or two steps at a time Conventionally the empty composition is counted as the sole composition of 0, and there are no compositions of negative integers. There are 2 n−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 \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. The same argument shows that the number of compositions of n into exactly k parts (a k-composition) is given by the binomial coefficient {n-1\choose k-1} . Note that by summing over all possible numbers of parts we recover 2 n−1 as the total number of compositions of n: \sum_{k=1}^n {n-1 \choose k-1} = 2^{n-1}. For weak compositions, the number is {n+k-1\choose k-1} = {n+k-1 \choose n} , since each k-composition of n + k corresponds to a weak one of n by the rule a_1+a_2+ \ldots + a_k = n +k \quad \mapsto \quad (a_1 -1) + (a_2-1) + \ldots + (a_k - 1) = n It follows from this formula that the number of weak compositions of n into exactly k parts equals the number of weak compositions of k − 1 into exactly n + 1 parts. For A-restricted compositions, the number of compositions of n into exactly k parts is given by the extended binomial (or polynomial) coefficient \binom{k}{n}_{(1)_{a\in A}}=[x^n]\Big(\sum_{a\in A} x^a\Big)^k , where the square brackets indicate the extraction of the coefficient of x^n in the polynomial that follows it.

Enumerating compositions

We can enumerate the (k+1)-compositions of an integer n + 1 by first enumerating the k-combinations of the n integers 0 through n - 1. Let c_1 be the members of such a combination. Then a composition of n + 1 is given by n+1 = p_k + \ldots + p_1 + p_0 where p_k = n - c_k,\ p_{k-1} = c_k - c_{k-1},\ \ldots,\ p_1 = c_2 - c_1,\ p_0 = c_1 + 1 .

Homogeneous polynomials

The dimension of the vector space K[x_1, \ldots, x_n]_d of homogeneous polynomial of degree d in n variables over the field K is the number of weak compositions of d into n parts. In fact, a basis for the space is given by the set of monomials x_1^{d_1}\cdots x_n^{d_n} such that d_1 + \ldots + d_n = d . Since the exponents d_i are allowed to be zero, then the number of such monomials is exactly the number of weak compositions of d.

See also

Stars and bars (combinatorics)

References

External links

Partition and composition calculator

Text derived from https://en.wikipedia.org/w/index.php?oldid=1354923617 under CC BY-SA 4.0; modifications have been made.