23
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\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
    Commented Apr 30, 2011 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
    Commented Apr 30, 2011 at 23:04

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is also consistent with the following bijective identification of (a) and (c): starting with an odd composition of n, write each odd part as 2+2+...+2+1 and remove the final 1 to get a {1,2} composition of n-1; starting from a {1,2} composition of n-1, "annex" +1 and combine each 2+2+...+2+1 to a single odd part to get an odd composition of n. Note that the OP's example with n=5 happens(?) to show the compositions in the corresponding order: 2+2 = 2+1+1 = 1+2+1 = 1+1+2 = 1+1+1+1 becomes 5 = 3+1+1 = 1+3+1 = 1+1+3 = 1+1+1+1+1. $\endgroup$
    – Noam D. Elkies
    Commented Jun 9, 2020 at 12:05
  • 1
    $\begingroup$ @NoamD.Elkies Thanks for noticing the ordering. But my ordering for (b) doesn't match the bijection I know between between (a) and (b): Think of a composition of $n$ as a tiling and associate an $n-1$ digit binary number with a 0 if the $i$th and $(i+1)$st blocks are connected, a 1 if they are in different parts. E.g., $312 \sim 00110$. The mapping is to add 1s at the beginning and end of the string, then toggle each bit; $312 \sim 00110 \rightarrow 1001101 \rightarrow 0110010 \sim 2132$. Applying this to the set given in (a) gives a bijection to $2+2+2, 2+4, 3+3,4+2,6$, respectively. $\endgroup$
    – Brian Hopkins
    Commented Jun 9, 2020 at 14:40
  • $\begingroup$ @BrianHopkins Thanks for tracking this down! Don't think this should endanger my tenure! $\endgroup$
    – Douglas Lind
    Commented Jun 9, 2020 at 15:06
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\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
    Commented Feb 25, 2012 at 5:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .