# 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.

The link I have is a directory with a link to table of contents of the relevant issue, and the article (scanned, "Hoggatt.pdf").

-
Thanks, just sent him email. Earlier I queried likely suspects Art Benjamin, Neville Robbins, and Doug Lind. It's possible there isn't an earlier source (Doug modestly said of the 1968 paper, "It's even possible this was an original result"), but with Euler's work on odd-part partitions at the beginning of that related field and Cayley looking at other restricted compositions... –  Brian Hopkins May 19 '11 at 3:50
@Brian: Keep us posted if you learn anything! –  amWhy May 19 '11 at 4:05
Kimberling: "This is one of many historical questions I WISH I could help with. I’d like to see the results of your search when ready." –  Brian Hopkins May 19 '11 at 13:20
Thanks for spending time on this. It's great that Fibonacci Quarterly has made their archives available electronically. I've checked out their 1968 & 1969 papers, along with Moser & Whitney 1961 that motivated them, without finding anything more about this particular brand of restricted composition. –  Brian Hopkins May 19 '11 at 18:15
@Brian: it's been my pleasure...If I have time later, perhaps I'll try some more "tracking"...but I'm impressed with what you've already "uncovered" ! –  amWhy May 19 '11 at 18:31