# Fibonacci, compositions, history

There are three basic families of restricted compositions (ordered partitions) that are enumerated by the Fibonacci numbers (with offsets):

a) compositions with parts from the set {1,2} (e.g., 2+2 = 2+1+1 = 1+2+1 = 1+1+2 = 1+1+1+1)

b) compositions that do not have 1 as a part (e.g., 6 = 4+2 = 3+3 = 2+4 = 2+2+2)

c) compositions that only have odd parts (e.g., 5 = 3+1+1 = 1+3+1 = 1+1+3 = 1+1+1+1+1)

The connection between (a) & the Fibonacci numbers traces back to the analysis of Vedic poetry in the first millennium C.E., at least (Singh, Hist. Math. 12, 1985).

Cayley made the connection to (b) in 1876 (Messenger of Mathematics).

$\bullet$ Who first established the connection with (c), odd-part compositions? It was known by 1968 (Hoggatt & Lind, J. Comb. Th.), but I suspect it was done before that. Thanks for any assistance, especially with citations.

By the way, it is a nice exercise to give combinatorial proofs of why each family is counted by the Fibonacci numbers, and establish direct connections between each pair of families.

PS: Apologies for cross-posting from MathOverflow, want to see if the audience here has more knowledge of such things.

-

Given your interest in this matter, you may very well have encountered the OEIS entry:

"F(n) = number of compositions of n into odd parts; e.g. F(6) counts 1+1+1+1+1+1, 1+1+1+3, 1+1+3+1, 1+3+1+1, 1+5, 3+1+1+1, 3+3, 5+1. - Clark Kimberling (ck6(AT)evansville.edu), Jun 22 2004"

Perhaps you can learn more by contacting Clark Kimberling, at email listed above, who may very well have researched the origins of this observation?

Edit:

I did find a scanned copy of an article authored by Hoggatt and Lind ("Combinations and Fibonacci Numbers", The Fibonacci Quarterly, Vol. 7 (3), 1969), which includes a reference to their 1968 publication. No direct reference is given to their claim and demonstration of the property in question, and it seems to be, as Lind commented in your communication, original.) However, the opening section of this paper discussed the motivation for it, including references to earlier work upon which the authors hope to generalize.