El Canto De Las Aves Problema

Question

Para mi los algoritmos de clase, el profesor tiene esta pregunta como crédito extra:

El Phicitlius Bauber de aves se cree que nunca cantar la misma canción dos veces.
Sus canciones son siempre de 10 segundos de duración y consiste en una serie de notas que son de tono bajo o alto y son de 1 o 2 segundos de duración.
Cuántos diferentes canciones de la Bauber pájaro cantar?

Esto me parece un problema combinatorio, pero estoy teniendo problemas para averiguar la fórmula exacta a utilizar para el ajuste incluye variables de 10 segundos de longitud, 2 notas y 2 nota períodos.

Al principio, pensé que $\binom{10}{2}*\binom{10}{2}$ puede ser una solución, ya que se adapta a encontrar todas las combinaciones de ambos y se multiplica el total.

Mi problema es este que resulta en un total de 2025 posibles canciones, y esto sólo parece un poco en el lado de baja.

Cualquier ayuda es apreciada.

Answer 1

Voy a trabajar bajo el supuesto de que dos sucesivos de 1 segundo de las notas del mismo tono es distinto de una simple 2-segunda nota de que el terreno de juego.

Deje $f(n)$ ser el número de los distintos $n$-segundo canto del pájaro puede cantar. El pájaro tiene cuatro opciones para el arranque de la canción: 1-segunda baja, 1-segunda alta, 2-segunda baja, y 2-segundo alto. Esto le da a la recursividad $$ f(n) = 2f(n-1) + 2f(n-2), $$ con $f(0) = 1$$f(1) = 2$.

La ecuación característica asociada es $x^2 - 2x - 2 = 0$, que tiene raíces $x = 1 \pm \sqrt{3}$. Por lo tanto, obtenemos la solución general $$ f(n) = A(1 + \sqrt{3})^n + B(1 - \sqrt{3})^n. $$

Usando las condiciones iniciales, tenemos el sistema $$ \begin{align*} 1 &= A + B\\ 2 &= A(1 + \sqrt{3}) + B(1 - \sqrt{3}), \end{align*} $$ el que tiene la solución única $A = \frac{3 + \sqrt{3}}{6}$$B = \frac{3 - \sqrt{3}}{6}$.

Por último, tenemos $$ f(n) = \frac{3 + \sqrt{3}}{6}(1 + \sqrt{3})^n + \frac{3 - \sqrt{3}}{6}(1 - \sqrt{3})^n. $$

Para el problema en cuestión, queremos $$ f(10) = 18,272. $$

Answer 2

Sugerencia: el uso de la recursividad.

Usted sabe que la primera nota en la Bauber de pájaro de la canción es $1$ o $2$ segundos de duración. En el primer caso, el resto de la canción es $9$ segundos de duración; en el segundo caso, el resto de la canción es $8$ segundos de duración.

Por lo tanto, el número de $10$-segunda canciones es igual a dos veces (recuerde, la última nota puede ser bajo o alto) el número de $9$-segunda canciones más el número de $8$-segunda canciones. Se puede ver cómo solucionar el problema de aquí?

También, tenga en cuenta que por lo general es una mala idea para animar a los "buscando cosas para hacer con los números en el problema" como usted dijo que usted hizo con su primer intento, $\binom{10}{2}*\binom{10}{2}$. Aunque la fórmula de caza tiene sus usos (esp. al hacer el análisis dimensional, donde es esencial), si usted va a tratar de encontrar una fórmula en primer lugar, es una buena idea para comprobar la respuesta para casos pequeños (como $1$ segunda, $2$ segundos, etc) y luego extrapolar a partir de eso que tratar de adivinar las fórmulas de los ciegos.

Answer 3

Aquí es un no-recursiva solución.

Supongamos que hay $a$ 1s canciones y $b$ 2s canciones, por lo $a + 2b = 10$. El número total de canciones es $10 - b$.

Podemos contar el número de canciones por primera ignorando el tono y contar las formas en que el 1s y 2s canciones se puede pedir, entonces multiplicando por $2^{a+b}$.

Hay $a+1$ huecos entre las $a$ 1s canciones, así que queremos saber cuántas maneras $b$ 2s canciones caben en $a+1$ lagunas. Esto es $\binom{a+b}{b} = \binom{10-b}{b}$, como se muestra por Akash Kumar en esta respuesta.

Así que queremos

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