§26.11 Integer Partitions: Compositions

Notes:: See Andrews (1976, Chapter 4).
Defines:: $\mathop{c\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of compositions of $n$ and $\mathop{c\/}\nolimits\!\left(n\right)$ : number of compositions of $n$
Keywords:: Fibonacci numbers, partitions
Referenced by:: §24.15(iv)
Permalink:: http://dlmf.nist.gov/26.11

A composition is an integer partition in which order is taken into account. For example, there are eight compositions of 4: $4,3+1,1+3,2+2,2+1+1,1+2+1,1+1+2$ , and $1+1+1+1$ . $\mathop{c\/}\nolimits\!\left(n\right)$ denotes the number of compositions of $n$ , and $\mathop{c_{{m}}\/}\nolimits\!\left(n\right)$ is the number of compositions into exactly $m$ parts. $\mathop{c\/}\nolimits\!\left(\in\! T,n\right)$ is the number of compositions of $n$ with no 1’s, where again $T=\{ 2,3,4,\ldots\}$ . The integer 0 is considered to have one composition consisting of no parts:

26.11.1 $\mathop{c\/}\nolimits\!\left(0\right)=\mathop{c\/}\nolimits\!\left(\in\! T,0\right)=1.$

Symbols:: $\in$ : element of, $\mathop{c\/}\nolimits\!\left(n\right)$ : number of compositions of $n$ , $\mathop{c\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of compositions of $n$ and $T$ : set
Permalink:: http://dlmf.nist.gov/26.11.E1
Encodings:: TeX, pMML, png

Also,

26.11.2 $\mathop{c_{{m}}\/}\nolimits\!\left(0\right)=\delta _{{0,m}},$

Symbols:: $\delta _{{j,k}}$ : Kronecker delta, $\mathop{c\/}\nolimits\!\left(n\right)$ : number of compositions of $n$ and $m$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.11.E2
Encodings:: TeX, pMML, png

26.11.3 $\mathop{c_{{m}}\/}\nolimits\!\left(n\right)=\binom{n-1}{m-1},$

Symbols:: $\binom{m}{n}$ : binomial coefficient, $\mathop{c\/}\nolimits\!\left(n\right)$ : number of compositions of $n$ , $m$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.11.E3
Encodings:: TeX, pMML, png

26.11.4 $\sum _{{n=0}}^{{\infty}}\mathop{c_{{m}}\/}\nolimits\!\left(n\right)q^{n}=\frac{q^{m}}{(1-q)^{m}}.$

Symbols:: $\mathop{c\/}\nolimits\!\left(n\right)$ : number of compositions of $n$ , $m$ : nonnegative integer, $n$ : nonnegative integer and $q$ : parameter
Permalink:: http://dlmf.nist.gov/26.11.E4
Encodings:: TeX, pMML, png

The Fibonacci numbers are determined recursively by

26.11.5

$F_{0}=0$ ,

$F_{1}=1$ ,

$F_{n}=F_{{n-1}}+F_{{n-2}}$ , $n\geq 2$ .

Symbols:: $n$ : nonnegative integer and $F_{n}$ : Fibonacci numbers
Permalink:: http://dlmf.nist.gov/26.11.E5
Encodings:: TeX, TeX, TeX, pMML, pMML, pMML, png, png, png

26.11.6 $\mathop{c\/}\nolimits\!\left(\in\! T,n\right)=F_{{n-1}},$ $n\geq 1$ .

Symbols:: $\in$ : element of, $\mathop{c\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of compositions of $n$ , $n$ : nonnegative integer, $T$ : set and $F_{n}$ : Fibonacci numbers
Permalink:: http://dlmf.nist.gov/26.11.E6
Encodings:: TeX, pMML, png

Explicitly,

26.11.7 $F_{n}=\frac{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}}{2^{n}\,\sqrt{5}}.$

Symbols:: $n$ : nonnegative integer and $F_{n}$ : Fibonacci numbers
Permalink:: http://dlmf.nist.gov/26.11.E7
Encodings:: TeX, pMML, png

Additional information on Fibonacci numbers can be found in Rosen et al. (2000, pp. 140–145).