# §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: , and . denotes the number of compositions of , and is the number of compositions into exactly parts. is the number of compositions of with no 1’s, where again . The integer 0 is considered to have one composition consisting of no parts:

Also,

The Fibonacci numbers are determined recursively by

26.11.5
,
,
,.

Explicitly,

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