[Math] Fibonacci, compositions, history

Question

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

Answer 1

Found it! (Sorry, Doug, ha ha.)

Augustus de Morgan added several appendices to his Elements of Arithmetic in the fifth edition, 1846 (available on Google Books). Appendix 10, pages 201-210, is "on combinations." The relevant paragraph is on 202-203.

Required the number of ways in which a number can be compounded of odd numbers, different orders counting as different ways. If $a$ be the number of ways in which $n$ can be so made, and $b$ the number of ways in which $n+1$ can be made, then $a+b$ must be the number of ways in which $n+2$ can be made; for every way of making $12$ out of odd numbers is either a way of making $10$ with the last number increased by $2$, or a way of making $11$ with a $1$ annexed. Thus, $1+5+3+3$ gives $12$, formed from $1+5+3+1$ giving $10$. But $1+9+1+1$ is formed from $1+9+1$ giving $11$. Consequently, the number of ways of forming $12$ is the sum of the number of ways of forming $10$ and of forming $11$. Now, $1$ can only be formed in $1$ way, and $2$ can only be formed in $1$ way; hence $3$ can only be formed in $1+1$ or $2$ ways, $4$ in only $1+2$ or $3$ ways. If we take the series $1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$, $34$, $55$, $89$, &c. in which each number is the sum of the two preceding, then the $n$th number of this set is the number of ways (orders counting) in which $n$ can be formed of odd numbers. Thus, $10$ can be formed in $55$ ways, $11$ in $89$ ways, &c.

He established "increasing" and "annexing" in deriving the formula for the number of what we now call compositions. He does not treat either of the other two restrictions mentioned above.