What's New
About the Project
NIST
26 Combinatorial AnalysisProperties

§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(n) denotes the number of compositions of n, and cm(n) is the number of compositions into exactly m parts. c(T,n) is the number of compositions of n with no 1’s, where again T={2,3,4,}. The integer 0 is considered to have one composition consisting of no parts:

26.11.1 c(0)=c(T,0)=1.

Also,

26.11.2 cm(0)=δ0,m,
26.11.4 n=0cm(n)qn=qm(1-q)m.

The Fibonacci numbers are determined recursively by

26.11.5 F0 =0,
F1 =1,
Fn =Fn-1+Fn-2,
n2.
26.11.6 c(T,n)=Fn-1,
n1.

Explicitly,

26.11.7 Fn=(1+5)n-(1-5)n2n5.

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