9
$\begingroup$

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.

3 Answers 3

5

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. $

  • 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.2012-02-13
3

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.

2

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$

  • 0
    @BrianM.Scott Yes, you're right, thanks. Tried a new answer.2012-02-13