Hemachandra numbers

As I was watching this interview of Prof. Manjul Bhargava, I came across this nice relation between लघु, गुरू syllables of Sanskrut and Hemchandra numbers. Prof. Manjul Bhargava asks a simple question as follows -

If लघु = 1 beat and गुरू = 2 beats, in how many ways can you fill up 8 beats? This also related to theory of percussion instruments.

This question can be answered in two ways. Before trying that, let's count the number of ways for some small number of beats say 0,1,2,3,4.

• If number of bits = 0, ways to do it = {}, i.e. 0 ways

• If number of bits = 1, ways to do it = {1}, i.e. 1 ways

• If number of bits = 2, ways to do it = {11, 2}, i.e. 2 ways

• If number of bits = 3, ways to do it = {111, 12, 21} i.e. 3 ways

• If number of bits = 4, ways to do it = {1111, 112, 121, 211, 22} i.e. 5 ways

First way - the hard way!

If we want to fill up N bits, try to count the number of combinations - 
If N = 8. There are following combinations.

• Number of लघु = 0, number of गुरू = 4
• Number of ways to arrange these = 4C0 = 1
• Number of लघु = 2, number of गुरू = 3
• Number of ways to arrange these = 5C2 = 10
• Number of लघु = 4, number of गुरू = 2
• Number of ways to arrange these = 6C2 = 15
• Number of लघु = 6, number of गुरू = 1
• Number of ways to arrange these = 7C1 = 7
• Number of लघु = 8, number of गुरू = 0
• Number of ways to arrange these = 8C0 = 1

Total number of ways = 34. This is indeed 8th Hemchandra number as told in the lecture. But, this does not reveal the why this is 8th Hemchandra number. Next method reveals that.
 
Second way - the elegant way!

How can we fill in N beats if we know how to fill in lesser number of bits? Say, we know following ways to fill in 4 and 5 beats ->
4 : 121
5 : 1112
Then, to fill 6 beats, we just to need extend any way of filling 4 beats and append a गुरू e.g. from above 1212. We can also extend any way of filling 5 beats and append a लघु e.g. from above 11121.

Now, the connection with Hemchandra numbers is clear.
If F(N) is the number of ways to fill in a pattern of N beats then -
F(N) = F(N-1) + F(N-2)
Since as shown above, any pattern of N-1 beats can be extended by appending a लघु and any pattern of N-2 beats can be extended by appending a गुरू. So, F(N) is just the addition of those.

One might wonder why do we not need to place गुरू at all possible places in the pattern of F(N-2) (and similarly in F(N-1) for लघु). Here is the reason. Pick any pattern in F(N-2) say, 121. We need to put 2 now. If we put it in all places possible, here is what we get : 2121 1221 1221 1212. As we can see here, first patterns have patterns of 5 i.e. F(N-1) as prefixes so they are already being counted in F(N-1). So, it suffices to append it in the end only.