26 Combinatorial Analysis Properties 26.10 Integer Partitions: Other Restrictions 26.12 Plane Partitions

§26.11 Integer Partitions: Compositions

ⓘ

Defines:: $c\left(\NVar{n}\right)$ : number of compositions of $n$ , $c_{\NVar{m}}\left(\NVar{n}\right)$ : number of compositions of $n$ into exactly $m$ parts and $c\left(\NVar{\mathrm{condition}},\NVar{n}\right)$ : restricted number of compositions of $n$
Keywords:: Fibonacci numbers, compositions, partitions
Notes:: See Andrews (1976, Chapter 4).
Referenced by:: §18.5(i), §24.15(iv)
Permalink:: http://dlmf.nist.gov/26.11
See also:: Annotations for Ch.26

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.$
ⓘ Symbols: $\in$ : element of, $c\left(\NVar{n}\right)$ : number of compositions of $n$ , $c\left(\NVar{\mathrm{condition}},\NVar{n}\right)$ : restricted number of compositions of $n$ and $T$ : set Permalink: http://dlmf.nist.gov/26.11.E1 Encodings: TeX, pMML, png See also: Annotations for §26.11 and Ch.26

Also,

26.11.2		$c_{m}\left(0\right)=\delta_{0,m},$
ⓘ Symbols: $\delta_{\NVar{j},\NVar{k}}$ : Kronecker delta, $c_{\NVar{m}}\left(\NVar{n}\right)$ : number of compositions of $n$ into exactly $m$ parts and $m$ : nonnegative integer Permalink: http://dlmf.nist.gov/26.11.E2 Encodings: TeX, pMML, png See also: Annotations for §26.11 and Ch.26

26.11.3		$c_{m}\left(n\right)=\genfrac{(}{)}{0.0pt}{}{n-1}{m-1},$
ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$ : binomial coefficient, $c_{\NVar{m}}\left(\NVar{n}\right)$ : number of compositions of $n$ into exactly $m$ parts, $m$ : nonnegative integer and $n$ : nonnegative integer Permalink: http://dlmf.nist.gov/26.11.E3 Encodings: TeX, pMML, png See also: Annotations for §26.11 and Ch.26

26.11.4		$\sum_{n=0}^{\infty}c_{m}\left(n\right)q^{n}=\frac{q^{m}}{(1-q)^{m}}.$
ⓘ Symbols: $c_{\NVar{m}}\left(\NVar{n}\right)$ : number of compositions of $n$ into exactly $m$ parts, $m$ : nonnegative integer, $n$ : nonnegative integer and $q$ : parameter Permalink: http://dlmf.nist.gov/26.11.E4 Encodings: TeX, pMML, png See also: Annotations for §26.11 and Ch.26

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$ .
ⓘ Symbols: $\in$ : element of, $c\left(\NVar{\mathrm{condition}},\NVar{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 See also: Annotations for §26.11 and Ch.26

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 Referenced by: (18.5.4_5) 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).

26.10 Integer Partitions: Other Restrictions 26.12 Plane Partitions

NIST

Site Privacy Accessibility Privacy Program Copyrights Vulnerability Disclosure No Fear Act Policy FOIA Environmental Policy Scientific Integrity Information Quality Standards Commerce.gov Science.gov USA.gov