Composition (combinatorics)

Last updated November 21, 2024

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 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ⁿ⁻¹ distinct compositions.

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.^[1]

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.

Note that the ancient Sanskrit sages discovered many years before Fibonacci that the number of compositions of any natural number n as the sum of 1's and 2's is the nth Fibonacci number! Note that these are not general compositions as defined above because the numbers are restricted to 1's and 2's only.

1=1 (1)
2=1+1=2 (2)
3=1+1+1=1+2=2+1 (3)
4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2 (5)
5=1+1+1+1+1=1+1+1+2=1+1+2+1=1+2+1+1=2+1+1+1=1+2+2=2+1+2=2+2+1 (8)
6 will have 13 combinations etc.

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. 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ⁿ⁻¹ 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}]\left(\sum _{a\in A}x^{a}\right)^{k}$ , where the square brackets indicate the extraction of the coefficient of $x^{n}$ in the polynomial that follows it.^[2]

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.

Related Research Articles

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the polynomial $(x + y) n$ into a sum involving terms of the form $ax b y c$ , where the exponents $b$ and $c$ are nonnegative integers with $b + c = n$ , and the coefficient $a$ of each term is a specific positive integer depending on $n$ and $b$ . For example, for $n = 4$ ,

In mathematics, Pascal's triangle is an infinite triangular array of the binomial coefficients which play a crucial role in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although other mathematicians studied it centuries before him in Persia, India, China, Germany, and Italy.

In mathematics, the discriminant of a polynomial is a quantity that depends on the coefficients and allows deducing some properties of the roots without computing them. More precisely, it is a polynomial function of the coefficients of the original polynomial. The discriminant is widely used in polynomial factoring, number theory, and algebraic geometry.

<span class="mw-page-title-main">Factorization</span> (Mathematical) decomposition into a product

In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, $3 \times 5$ is an integer factorization of $15$ , and $(x - 2)(x + 2)$ is a polynomial factorization of $x 2 - 4$ .

In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book Methodus differentialis (1730). They were rediscovered and given a combinatorial meaning by Masanobu Saka in 1782.

Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900. It is the challenge to provide a general algorithm that, for any given Diophantine equation, can decide whether the equation has a solution with all unknowns taking integer values.

In number theory and combinatorics, a partition of a non-negative 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 the same partition. For example, $4$ can be partitioned in five distinct ways:

In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form, by some expression involving operations on the formal series.

In mathematics, a polynomial sequence, i.e., a sequence of polynomials indexed by non-negative integers $in which the index of each polynomial equals its degree, is said to be of binomial type if it satisfies the sequence of identities$

In mathematics, the falling factorial is defined as the polynomial

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

126 is the natural number following 125 and preceding 127.

In combinatorial mathematics, the Bell polynomials, named in honor of Eric Temple Bell, are used in the study of set partitions. They are related to Stirling and Bell numbers. They also occur in many applications, such as in Faà di Bruno's formula.

In mathematics, specifically in commutative algebra, the elementary symmetric polynomials are one type of basic building block for symmetric polynomials, in the sense that any symmetric polynomial can be expressed as a polynomial in elementary symmetric polynomials. That is, any symmetric polynomial $P$ is given by an expression involving only additions and multiplication of constants and elementary symmetric polynomials. There is one elementary symmetric polynomial of degree $d$ in $n$ variables for each positive integer $d \leq n$ , and it is formed by adding together all distinct products of $d$ distinct variables.

In mathematics the nth central binomial coefficient is the particular binomial coefficient

In mathematics, a univariate polynomial of degree $n$ with real or complex coefficients has $n$ complex roots, if counted with their multiplicities. They form a multiset of $n$ points in the complex plane. This article concerns the geometry of these points, that is the information about their localization in the complex plane that can be deduced from the degree and the coefficients of the polynomial.

In the mathematical field of combinatorics, the q-Pochhammer symbol, also called the q-shifted factorial, is the product $with It is a q -analog of the Pochhammer symbol, in the sense that The q -Pochhammer symbol is a major building block in the construction of q -analogs; for instance, in the theory of basic hypergeometric series, it plays the role that the ordinary Pochhammer symbol plays in the theory of generalized hypergeometric series.$

In combinatorics, a lattice path $L$ in the $d$ -dimensional integer lattice ⁠ $⁠$ of length $k$ with steps in the set $S$ , is a sequence of vectors ⁠ $⁠$ such that each consecutive difference $lies in S . A lattice path may lie in any lattice in ⁠ ⁠, but the integer lattice ⁠ ⁠ is most commonly used.$

Narayana polynomials are a class of polynomials whose coefficients are the Narayana numbers. The Narayana numbers and Narayana polynomials are named after the Canadian mathematician T. V. Narayana (1930–1987). They appear in several combinatorial problems.

References

↑ Heubach, Silvia; Mansour, Toufik (2004). "Compositions of n with parts in a set". Congressus Numerantium . 168: 33–51. CiteSeerX 10.1.1.484.5148 .
↑ Eger, Steffen (2013). "Restricted weighted integer compositions and extended binomial coefficients" (PDF). Journal of Integer Sequences . 16.

Heubach, Silvia; Mansour, Toufik (2009). Combinatorics of Compositions and Words. Discrete Mathematics and its Applications. Boca Raton, Florida: CRC Press. ISBN 978-1-4200-7267-9. Zbl 1184.68373.

External links

Partition and composition calculator

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Heubach, Silvia; Mansour, Toufik (2004). "Compositions of n with parts in a set". Congressus Numerantium . 168: 33–51. CiteSeerX 10.1.1.484.5148 .

[2] Eger, Steffen (2013). "Restricted weighted integer compositions and extended binomial coefficients" (PDF). Journal of Integer Sequences . 16.

[1]

[2]