Narayana's Cows and Delayed Morphisms

by Jean-Paul Allouche and Tom Johnson

     Six or eight years ago one of us (T.J.) found a German edition of a little book on the history of mathematics by a Ukranian scholar named Andrej Grigorewitsch Konforowitsch. The book was full of curious information, but I was particularly struck by the following, which Konforowitsch attributed to Narayana, an Indian mathematician in the 14th century:

     A cow produces one calf every year. Beginning in its fourth year, each calf produces one calf at the beginning of each year. How many cows and calves are there altogether after 20 years?

     In working this out, T.J. came to know a unique numerical sequence, and a year or so later I found a way to translate this into a composition called Narayana's Cows. It begins with the original cow and her first calf: long-short. The second year she has another calf: long-short-short. The third year: long-short-short-short. Then in the fourth year, the first calf also becomes a mother and the herd grows from four to six: long-short-short-short-long-short. The music continues like this, though it doesn't go all the way to the 20th year, because by the 17th year there are already 872 cows and calves and 15 minutes of music.

     Many things can be said about the mathematics of Narayana's cows, about different ways to translate them into music, about the point at which the calves begin to outnumber the cows, about the rate of population increase, the limit which this rate approaches, and so on. The essence of the problem, however, is simply the sequence resulting as the years go by: 1, 1, 1, 2, 3, 4, 6, 9, 13... Like the Fibonacci sequence, each number is calculated by adding earlier numbers, but instead of adding the two previous numbers, as one does for the Fibonacci series, one adds the previous number in the sequence plus the number two places before that.

     S_n = S_n-1 + S_n-3.

     The last number above is 13 (9 + 4) and the next must be 19 (13 + 6).

     Last year, as T.J. was writing Self-Similar Melodies, he decided to investigate this further and include a chapter on "Transforming with Delays." What if Narayana's cows gave birth already in their third year, instead of the fourth? What would happen to the population growth, and to the music, if they had to wait until the fifth year, or the sixth?

     This can perhaps be best explained if we forget about cows and calves and work with the Thue-Morse sequence, a binary automaton that has already been studied rather extensively. In the classic case, 0 goes to 1 0, 0 goes to 0 1, there are no delays, and the population doubles with each transformation. S_n = S_n-1 + S_n-1:

0       1
0   1   1   0
0 1 1 0 1 0 0 1
0110100110010110
...

     This is equivalent to having calves that are born in one year and become mother cows the very next year. What happens to the Thue-Morse population if its digits give birth in their third year instead of their second? Well, instead of doubling with each transformation, they now follow the Fibonacci series, S_n = S_n-1 + S_n-2:

0
0
0       1
0    1  1 
0  1 1  1  0
0 11 10 1 00
0111010010001
...

     If the ones and zeros give birth in their fourth year, the Thue-Morse series grows at the same rate as the Narayana series, S_n = S_n-1 + S_n-3:

0
0
0
0        1 
0     1  1
0   1 1  1          
0  11 1  1  0
0 111 1 01 00
0111101001000
...

     Let's take that one step further and have each digit divide into two digits in its fifth stage of existence. Now the formula is S_n = S_n-1 + S_n-4, and the Narayana series of 1 1 1 2 3 4 6 9 13... becomes 1 1 1 1 2 3 4 5 7...:

0
0
0
0
0      1
0    1 1
0   11 1
0  111 1
0 1111 1 0
0111110100

     One day I noticed that there was an easier way of calculating this: Each line was actually just a repetition of the sequence one line above, followed by the inversion of the sequence four lines above. Why was the line inverted? Since I often like to interpret such sequences as melodies that ascend with 1 and descend with zeros, I wanted to know whether the ones would continue to outnumber the zeros as they do here.

     Narayana's little problem had led me to one particularly musical sequence, but now I was confronted with a whole family of sequences, which I didn't really understand, but which seemed to have strong musical possibilities. I showed the problem to my friend and colleague Jean-Paul Allouche, who works extensively with "finite automata." He was quite interested, because he said that mathematics had not really studied "delayed morphisms" of this sort, and that there were some observations to be made here that could be useful in current mathematics, and which in turn, might also be useful to composers working with logical sequences.