# §26.11 Integer Partitions: Compositions

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

Also,

 26.11.2 $\mathop{c_{m}\/}\nolimits\!\left(0\right)=\delta_{0,m},$
 26.11.3 $\mathop{c_{m}\/}\nolimits\!\left(n\right)=\binom{n-1}{m-1},$
 26.11.4 $\sum_{n=0}^{\infty}\mathop{c_{m}\/}\nolimits\!\left(n\right)q^{n}=\frac{q^{m}}% {(1-q)^{m}}.$

The Fibonacci numbers are determined recursively by

 26.11.5 $\displaystyle F_{0}$ $\displaystyle=0$, $\displaystyle F_{1}$ $\displaystyle=1$, $\displaystyle F_{n}$ $\displaystyle=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$.

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