§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$. $c\left(n\right)$ denotes the number of compositions of $n$, and $c_{m}\left(n\right)$ is the number of compositions into exactly $m$ parts. $c\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 $c\left(0\right)=c\left(\in\!T,0\right)=1.$

Also,

 26.11.2 $c_{m}\left(0\right)=\delta_{0,m},$
 26.11.3 $c_{m}\left(n\right)=\genfrac{(}{)}{0.0pt}{}{n-1}{m-1},$
 26.11.4 $\sum_{n=0}^{\infty}c_{m}\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 See also: Annotations for §26.11 and Ch.26
 26.11.6 $c\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 See also: Annotations for §26.11 and Ch.26

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