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

Who first established the connection with (c), odd-part compositions? It was known by 1969 (Hoggatt & Lind, Fib. Quart.), but I suspect it was done before that. Thanks for any assistance, especially with citations.

BOUNTY! Not sure how much this incentivizes responses, but it would be nice to figure this out. By the way, I have queried Art Benjamin, Neville Robbins, and Doug Lind about this (Doug modestly mentioned of the 1969 article It's even possible this was an original result.'').

-
Did you look in Hardy and Wright? I'm not at work so don't have access to my copy, but my memory is that they talk about odd part compositions in their chapter on partitions, and their references (at the end of each section) are sometimes short but often to the point. – Kevin Buzzard Apr 30 '11 at 22:26
Thanks, Kevin. I don't find anything about compositions in Hardy & Wright (I have the fifth edition). All of these restricted compositions are discussed in Heubach & Mansour's 2010 Combinatorics of Compositions and Words, but their history does not go back very far (nor do they claim to trace back to the very first sources). – Brian Hopkins Apr 30 '11 at 23:04