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.'').

  • $\begingroup$ 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. $\endgroup$ – Kevin Buzzard Apr 30 '11 at 22:26
  • $\begingroup$ 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). $\endgroup$ – Brian Hopkins Apr 30 '11 at 23:04

I make this an answer instead of a comment so as to bring it to the attention of others.

Using Google Books search for compositions "odd parts" Fibonacci brings up several modern combinatorics texts which might have a reference for the result. It also brings up a 1961 Canadian journal which only has a snippet view, but which might yield useful information. If the poster is still interested in tracking down the source, the search results may prove fruitful, especially as they may not have been available at the time of the first posting.

Gerhard "Ask Me About System Design" Paseman, 2012.02.10

  • $\begingroup$ Thanks for coming back to this, Gerhard. The article you pointed me to is available free online. It does include both topics, but not the case I mentioned. Odd part compositions come up in Example 2, and Fibonacci numbers in Example 3 (which foreshadows what Agarwal called "n-colour compositions" in a 2000 paper!). These interesting results are more involved than the number of compositions with odd parts being counted by Fibonacci numbers, which again makes me think that had to be known before. Of course the article has no references. cms.math.ca/cmb/v4/cmb1961v04.0039-0043.pdf $\endgroup$ – Brian Hopkins Feb 25 '12 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.