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

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

§26.11 Integer Partitions: Compositions

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!