Composition (combinatorics)

<h2 id="examples">Examples</h2>

The sixteen compositions of 5 are:

<ul><li>5</li>
<li>4 + 1</li>
<li>3 + 2</li>
<li>3 + 1 + 1</li>
<li>2 + 3</li>
<li>2 + 2 + 1</li>
<li>2 + 1 + 2</li>
<li>2 + 1 + 1 + 1</li>
<li>1 + 4</li>
<li>1 + 3 + 1</li>
<li>1 + 2 + 2</li>
<li>1 + 2 + 1 + 1</li>
<li>1 + 1 + 3</li>
<li>1 + 1 + 2 + 1</li>
<li>1 + 1 + 1 + 2</li>
<li>1 + 1 + 1 + 1 + 1.</li></ul>
Compare this with the seven partitions of 5:

<ul><li>5</li>
<li>4 + 1</li>
<li>3 + 2</li>
<li>3 + 1 + 1</li>
<li>2 + 2 + 1</li>
<li>2 + 1 + 1 + 1</li>
<li>1 + 1 + 1 + 1 + 1.</li></ul>
It is possible to put constraints on the parts of the compositions. For example the five compositions of 5 into distinct terms are:

<ul><li>5</li>
<li>4 + 1</li>
<li>3 + 2</li>
<li>2 + 3</li>
<li>1 + 4.</li></ul>
Compare this with the three partitions of 5 into distinct terms:

<ul><li>5</li>
<li>4 + 1</li>
<li>3 + 2.</li></ul>
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.

<ul><li>1=1 (1)</li>
<li>2=1+1=2 (2)</li>
<li>3=1+1+1=1+2=2+1 (3)</li>
<li>4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2 (5)</li>
<li>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)</li>
<li>6 will have 13 combinations etc.</li></ul>
<h2 id="number-of-compositions">Number of compositions</h2>

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

(
          
        
        
        
          
            
              
                1
                
                ◻
                
                1
                
                ◻
                
                …
                
                ◻
                
                1
                
                ◻
                
                1
              
              ⏞
            
          
          
            n
          
        
        
        
          
            )
          
        
      
    
    {\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 <a href="/facts/Binomial_coefficient/Tsx7eY5h">binomial coefficient</a> 
 
 
 
 
 
 
 (
 
 
 
 n
 −
 1
 
 
 k
 −
 1
 
 
 
 )
 
 
 
 
 
 {\displaystyle {n-1 \choose k-1}}
 
. Note that by summing over all possible numbers of parts we recover 2n−1 as the total number of compositions of n:

∑
          
            k
            =
            1
          
          
            n
          
        
        
          
            
              (
            
            
              
                n
                −
                1
              
              
                k
                −
                1
              
            
            
              )
            
          
        
        =
        
          2
          
            n
            −
            1
          
        
        .
      
    
    {\displaystyle \sum _{k=1}^{n}{n-1 \choose k-1}=2^{n-1}.}

For weak compositions, the number is 
 
 
 
 
 
 
 (
 
 
 
 n
 +
 k
 −
 1
 
 
 k
 −
 1
 
 
 
 )
 
 
 
 =
 
 
 
 (
 
 
 
 n
 +
 k
 −
 1
 
 n
 
 
 )
 
 
 
 
 
 {\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

a
          
            1
          
        
        +
        
          a
          
            2
          
        
        +
        …
        +
        
          a
          
            k
          
        
        =
        n
        +
        k
        
        ↦
        
        (
        
          a
          
            1
          
        
        −
        1
        )
        +
        (
        
          a
          
            2
          
        
        −
        1
        )
        +
        …
        +
        (
        
          a
          
            k
          
        
        −
        1
        )
        =
        n
      
    
    {\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 
 
 
 
 
 
 
 
 (
 
 
 k
 n
 
 
 )
 
 
 
 
 (
 1
 
 )
 
 a
 ∈
 A
 
 
 
 
 =
 [
 
 x
 
 n
 
 
 ]
 
 
 (
 
 
 ∑
 
 a
 ∈
 A
 
 
 
 x
 
 a
 
 
 
 )
 
 
 k
 
 
 
 
 {\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 <a href="/facts/Coefficient/5Hwq2Wuq">coefficient</a> of 
 
 
 
 
 x
 
 n
 
 
 
 
 {\displaystyle x^{n}}
 
 in the polynomial that follows it.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

<h2 id="homogeneous-polynomials">Homogeneous polynomials</h2>
The dimension of the vector space 
 
 
 
 K
 [
 
 x
 
 1
 
 
 ,
 …
 ,
 
 x
 
 n
 
 
 
 ]
 
 d
 
 
 
 
 {\displaystyle K[x_{1},\ldots ,x_{n}]_{d}}
 
 of <a href="/facts/Homogeneous_polynomial/WUHL7Kct">homogeneous polynomial</a> 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
 
 
 
 
 ⋯
 
 x
 
 n
 
 
 
 d
 
 n
 
 
 
 
 
 
 {\displaystyle x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}}
 
 such that 
 
 
 
 
 d
 
 1
 
 
 +
 …
 +
 
 d
 
 n
 
 
 =
 d
 
 
 {\displaystyle d_{1}+\ldots +d_{n}=d}
 
. Since the exponents 
 
 
 
 
 d
 
 i
 
 
 
 
 {\displaystyle d_{i}}
 
 are allowed to be zero, then the number of such monomials is exactly the number of weak compositions of d.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Stars_and_bars_(combinatorics)/UXptBeup">Stars and bars (combinatorics)</a></li></ul>

<ul><li>Heubach, Silvia; Mansour, Toufik (2009). Combinatorics of Compositions and Words. Discrete Mathematics and its Applications. Boca Raton, Florida: CRC Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-4200-7267-9. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:1184.68373">1184.68373</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.se16.info/js/partitions.htm">Partition and composition calculator</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn: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. <a href="/wiki/Silvia_Heubach" target="_blank">/wiki/Silvia_Heubach</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Eger, Steffen (2013). "Restricted weighted integer compositions and extended binomial coefficients" (PDF). Journal of Integer Sequences. 16. <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Eger/eger6.pdf" target="_blank">https://cs.uwaterloo.ca/journals/JIS/VOL16/Eger/eger6.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
</ol>

Composition (combinatorics) open-in-new

Composition (combinatorics)