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:
The Fibonacci numbers are determined recursively by
Additional information on Fibonacci numbers can be found in Rosen et al. (2000, pp. 140–145).