Composition (combinatorics)

The 32 compositions of 6

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 2 + 1 + 1 + 1
. . .
1 + 5
6

The 11 partitions of 6

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
3 + 1 + 1 + 1
. . .
3 + 3
6

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.

Using the Fibonacci sequence to count the {1, 2}-restricted compositions of n, for example, 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ⁿ⁻¹ 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

${\displaystyle {\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 ${\displaystyle {n-1 \choose k-1}}$. Note that by summing over all possible number of parts we recover 2ⁿ⁻¹ as the total number of compositions of n:

${\displaystyle \sum _{k=1}^{n}{n-1 \choose k-1}=2^{n-1}.}$

For weak compositions, the number is ${\displaystyle {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

${\displaystyle 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 ${\displaystyle {\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 ${\displaystyle x^{n}}$ in the polynomial that follows it.[2]

The dimension of the vector space ${\displaystyle 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 n. In fact, a basis for the space is given by the set of monomials ${\displaystyle x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}}$ such that ${\displaystyle d_{1}+\ldots +d_{n}=d}$. Since the exponents ${\displaystyle d_{i}}$ are allowed to be zero, then the number of such monomials is exactly by the number of weak compositions of n.

• Stars and bars (combinatorics)

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

• Partition and composition calculator