Editing Composition (combinatorics)

{{Short description|Mathematical concept}}
{{Other uses of|Composition}}

In [[mathematics]], a '''composition''' of an [[integer]] ''n'' is a way of writing ''n'' as the [[summation|sum]] of a sequence of (strictly) [[positive integer]]s. 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 <span style="white-space:nowrap" >2<sup>''n''−1</sup></span> distinct compositions.
[[File:Binary and compositions 4.svg|thumb|center|600px|[[Bijection]] between 3 bit [[binary numeral system|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 integer]]s. 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&nbsp;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''.<ref>
{{cite journal
 | last1=Heubach | first1=Silvia | author1-link = Silvia Heubach
 | last2=Mansour | first2=Toufik | author2-link = Toufik Mansour
 | year=2004
 | title=Compositions of n with parts in a set
 | journal=[[Congressus Numerantium]] | volume=168 | pages=33–51
 | citeseerx=10.1.1.484.5148 }}</ref>

==Examples==
[[File:Compositions of 6.svg|thumb|The 32 compositions of 6<br><br>1 + 1 + 1 + 1 + 1 + 1<br>2 + 1 + 1 + 1 + 1<br>1 + 2 + 1 + 1 + 1<br>. . .<br>1 + 5<br>6]]
[[File:Partitions of 6.svg|thumb|The 11 partitions of 6<br><br>1 + 1 + 1 + 1 + 1 + 1<br>2 + 1 + 1 + 1 + 1<br>3 + 1 + 1 + 1<br>. . .<br>3 + 3<br>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.

==Number of compositions==
[[File:pascal_triangle_compositions.svg|thumb|The numbers of compositions of ''n''{{hairsp}}+1 into ''k''{{hairsp}}+1 ordered partitions form [[Pascal's triangle]] ]]
[[File:Fibonacci_climbing_stairs.svg|thumb|Using the [[Fibonacci sequence]] to count the {1, 2}-restricted compositions of ''n'', {{nowrap|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<sup>''n''−1</sup> compositions of ''n''&nbsp;&ge;&nbsp;1; here is a proof:

Placing either a plus sign or a comma in each of the ''n''&nbsp;&minus;&nbsp;1 boxes of the array
:<math>
    \big(\,
      \overbrace{1\, \square\, 1\, \square\, \ldots\, \square\, 1\,
      \square\, 1}^n\,
    \big)
</math>

produces a unique composition of ''n''. Conversely, every composition of ''n'' determines an assignment of pluses and commas. Since there are ''n''&nbsp;&minus;&nbsp;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]] <math>{n-1\choose k-1}</math>.  Note that by summing over all possible numbers of parts we recover 2<sup>''n''−1</sup> as the total number of compositions of ''n'':

: <math> \sum_{k=1}^n {n-1 \choose k-1} = 2^{n-1}.</math>

For weak compositions, the number is <math>{n+k-1\choose k-1} = {n+k-1 \choose n}</math>, since each ''k''-composition of ''n''&nbsp;+&nbsp;''k'' corresponds to a weak one of&nbsp;''n'' by the rule

:<math>
  a_1+a_2+ \ldots + a_k = n +k \quad \mapsto \quad (a_1 -1) + (a_2-1) + \ldots + (a_k - 1) = n
</math>

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 <math>\binom{k}{n}_{(1)_{a\in A}}=[x^n]\left(\sum_{a\in A} x^a\right)^k</math>, where the square brackets indicate the extraction of the [[coefficient]] of <math>x^n</math> in the polynomial that follows it.<ref>
{{cite journal
 | last1=Eger | first1=Steffen
 | year=2013
 | title=Restricted weighted integer compositions and extended binomial coefficients
 | journal=[[Journal of Integer Sequences]] | volume=16
 | url=https://cs.uwaterloo.ca/journals/JIS/VOL16/Eger/eger6.pdf
}}</ref>

==Homogeneous polynomials==
The dimension of the vector space <math>K[x_1, \ldots, x_n]_d</math> 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 <math>x_1^{d_1}\cdots x_n^{d_n}</math> such that <math>d_1 + \ldots + d_n = d</math>. Since the exponents <math>d_i</math> 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==
{{reflist}}
*{{cite book |last1=Heubach |first1=Silvia |last2=Mansour |first2=Toufik |year=2009 |title=Combinatorics of Compositions and Words |series=Discrete Mathematics and its Applications |publisher=CRC Press |location=Boca Raton, Florida |isbn=978-1-4200-7267-9 |zbl=1184.68373}}

==External links==
*[http://www.se16.info/js/partitions.htm Partition and composition calculator]

[[Category:Integer partitions]]