Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For my algorithms class, the professor has this question as extra credit:

The Phicitlius Bauber bird is believed to never sing the same song twice.
Its songs are always 10 seconds in length and consist of a series of notes that are either high or low pitched and are either 1 or 2 seconds long.
How many different songs can the Bauber bird sing?

This strikes me as a combinatorial problem, but I'm having trouble figuring out the exact formula to use to fit the included variables of 10 seconds length, 2 notes and 2 note periods.

At first, I thought that $\binom{10}{2}*\binom{10}{2}$ can be a solution, since it fits finding all combinations of both and multiplies the total.

My issue is this results in a total of 2025 possible songs, and this just seems a little on the low side.

Any assistance is appreciated.

share|improve this question

3 Answers 3

up vote 5 down vote accepted

I'm going to work under the assumption that two successive 1-second notes of the same pitch is distinct from a single 2-second note of that pitch.

Let $f(n)$ be the number of distinct $n$-second songs the bird can sing. The bird has four options for starting the song: 1-second low, 1-second high, 2-second low, and 2-second high. This gives the recursion $$ f(n) = 2f(n-1) + 2f(n-2), $$ with $f(0) = 1$ and $f(1) = 2$.

The associated characteristic equation is $x^2 - 2x - 2 = 0$, which has roots $x = 1 \pm \sqrt{3}$. Thus, we get the general solution $$ f(n) = A(1 + \sqrt{3})^n + B(1 - \sqrt{3})^n. $$

Using the initial conditions, we have the system $$ \begin{align*} 1 &= A + B\\ 2 &= A(1 + \sqrt{3}) + B(1 - \sqrt{3}), \end{align*} $$ which has the unique solution $A = \frac{3 + \sqrt{3}}{6}$ and $B = \frac{3 - \sqrt{3}}{6}$.

Finally, we have $$ f(n) = \frac{3 + \sqrt{3}}{6}(1 + \sqrt{3})^n + \frac{3 - \sqrt{3}}{6}(1 - \sqrt{3})^n. $$

For the problem at hand, we want $$ f(10) = 18,272. $$

share|improve this answer
1  
That's strange, f(2)=7. But as Mark Eichenlaub says, it should be 6. I think you made a mistake somewhere. –  Lopsy Feb 13 '12 at 21:52
2  
The roots should be $1\pm\sqrt3$, and $f(10)$ is considerably smaller; a hasty calculation made it $18272$. @Lopsy means that your formula for $f(n)$ gives $f(2)=7$. –  Brian M. Scott Feb 13 '12 at 21:55
    
Right, but your final equation with the radicals gives 7. I think I figured out what happened: the roots of that quadratic are 1+sqrt(3) and 1-sqrt(3), not 2+sqrt(3) and 2-sqrt(3) as you claim. –  Lopsy Feb 13 '12 at 21:56
    
Thanks for everyone's keen eyes. I believe I've caught all the errors now. –  Austin Mohr Feb 13 '12 at 22:16
2  
Now it’s good. I’d add just one comment: $10$ is a small enough number that in this case it’s easier just to use the recurrence than it is to find the general solution. –  Brian M. Scott Feb 13 '12 at 22:18

Hint: use recursion.

You know that the first note in the Bauber bird's song is either $1$ or $2$ seconds long. In the first case, the remainder of the song is $9$ seconds long; in the second case, the remainder of the song is $8$ seconds long.

Therefore, the number of $10$-second songs equals twice (remember, the last note can be low or high) the number of $9$-second songs plus the number of $8$-second songs. Can you see how to solve the problem from here?

Also, note that it's generally a bad idea to encourage "looking for things to do with the numbers in the problem" like you said you did with your first try, $\binom{10}{2}*\binom{10}{2}$. Although formula-hunting does have its uses (esp. when doing dimensional analysis, where it's essential), if you're going to try to find a formula first, it's a good idea to check the answer for small cases (like $1$ second, $2$ seconds, etc) and then extrapolate off of that than trying to guess formulae blind.

share|improve this answer

Here is a non-recursive solution.

Suppose there are $a$ 1s songs and $b$ 2s songs, so $a + 2b = 10$. The total number of songs is $10 - b$.

We can count the number of such songs by first ignoring pitch and counting the ways the 1s and 2s songs can be ordered, then multiplying by $2^{a+b}$.

There are $a+1$ gaps between the $a$ 1s songs, so we want to know how many ways $b$ 2s songs can fit into $a+1$ gaps. This is $\binom{a+b}{b} = \binom{10-b}{b}$, as shown by Akash Kumar in this answer.

So we want

$$\sum_{b=0}^{5} 2^{10 - b}\dbinom{10 - b}{b} = 18,272$$

share|improve this answer
2  
But you can’t break the ten-second interval into $2$-second chunks, because a $2$-second note can overlap chunks. –  Brian M. Scott Feb 13 '12 at 21:59
    
@BrianM.Scott Yes, you're right, thanks. Tried a new answer. –  Mark Eichenlaub Feb 13 '12 at 23:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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