Digital Library of Mathematical Functions

About the Project

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

§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 and $\mathop{c\/}\nolimits\!\left(n\right)$ : number of compositions of
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: , and . $\mathop{c\/}\nolimits\!\left(n\right)$ denotes the number of compositions of , and $\mathop{c_{{m}}\/}\nolimits\!\left(n\right)$ is the number of compositions into exactly parts. $\mathop{c\/}\nolimits\!\left(\in\!T,n\right)$ is the number of compositions of 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 , $\mathop{c\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of compositions of and : 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 and : 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 , : nonnegative integer and : 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 , : nonnegative integer, : nonnegative integer and : 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:: : 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 , : nonnegative integer, : 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:: : 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).

© 2010–2013 NIST / Privacy Policy / Disclaimer / Feedback; Version 1.0.6; Release date 2013-05-06 Math-Image version (See MathML) . A Printed Companionis available. 26.10 Integer Partitions: Other Restrictions 26.12 Plane Partitions