Voy a plantear en este post cinco problemas de combinatoria que son equivalentes al problema de los conejos de Fibonacci, en el sentido de que dan lugar a la misma sucesión (y a la misma recurrencia). La solución de cada uno de ellos se detiene en el modelo, es decir, en el razonamiento por recurrencia que conduce a plantearlo.
1. Subconjuntos sin consecutivos
¿De cuántas formas se puede elegir un subconjunto de $\{1,2,\ldots,n\}$ de manera que no contenga números consecutivos?
Solución
Sea $u_n$ el número de subconjuntos de $\{1,2,\ldots.n\}$ sin números consecutivos. Cada subconjunto aceptable según la restricción, ya sea que contiene el 1 o bien no lo contiene.
Si contiene el 1 entonces no puede contener el 2 y se ve que el número de subconjuntos que contienen el 1 es $u_{n-2}$ --pues es el número de subconjuntos de $\{3,4,\ldots,n\}$.
Por otro lado, si el subconjunto no contiene el 1, entonces el número de subconjuntos de esta clase son $u_{n-1}$ --dado que es el número de subconjuntos de $\{2,3,\ldots,n\}$.
En resumen, $u_n=u_{n-1}+u_{n-2}$. (Claramente, $u_1=1,u_2=2$ --se deja como ejercicio su justificación.)
2. n-Cadenas binarias con dos ceros consecutivos
¿De cuántas formas se puede construir una n-cadena de ceros y unos con dos ceros consecutivos?
Solución
Sea $u_n$ el número de cadenas binarias de longitud $n$ con dos ceros
consecutivos. Claramente, una cadena de longitud 1 no puede tener dos ceros consecutivos, y solamente hay una de longitud dos con dos ceros consecutivos. Es decir, $u_1=0,u_2=1$.
Consideremos ahora el caso general. Cada cadena de longitud $n$ con dos ceros consecutivos es de una de tres clases: empieza con 00 o con 01 o con 1.
Si empieza con 00, el resto de la cadena es una cadena de longitud $n-2$ sin restricción.
Por otro lado, si empieza con 01, el resto de la cadena es una cadena de longitud $n-2$ con dos ceros consecutivos.
Finalmente, si empieza con 1, el resto de la cadena es una cadena de longitud $n-1$ con dos ceros consecutivos.
En resumen, el modelo recursivo para este problema es:
$$u_n=2^{n-2}+u_{n-2}+u_{n-1}$$
con $u_1=0,u_2=1$
3. Sus dígitos son 1 y/o 2 y suman n
¿Cuántos números con 1 y 2 como dígitos son tales que éstos suman $n$? Ejemplo: 111, 12, 21 son los tres números que cumplen para $n=3$.
Solución
Sea $u_n$ el número de números que cumplen para $n$. Claramente, $u_1=1, u_2=2$. En el caso de $n$ mayor que 2, se puede razonar recursivamente como sigue:
Los números que cumplen se pueden clasificar en dos clases excluyentes y exhaustivas. Los que empiezan con 1 y los que empiezan con 2.
Si empiezan con 1, son $u_{n-1}$ --pues el problema se reduce a contar los números con 1 y 2 como dígitos y tales que éstos suman $n-1$.
Si empiezan con 2, son $U_{n-2}$ --siguiendo un razonamiento similar. Por tanto $u_n=u_{n-1}+u_{n-2}$.
Otra forma: Considerando el último dígito, éste puede ser 1 o bien 2. Los números que terminan en 2 son $u_{n-2}$ y los que terminan en 1 son $u_{n-2}$
4. n-Cadenas binarias sin unos consecutivos
¿De cuantas formas se puede formar una cadena de ceros y unos de longitud $n$ sin unos consecutivos?
Solución
Los números ya sea que inician con cero o bien con uno. Los que empiezan con cero son $u_{n-1}$ y los que empiezan con uno son $u_{n-2}$ --porque en realidad deben empezar con 10. Por tanto, $u_n=u_{n-1}+u_{n-2}$.
5. Tiempo de espera hasta dos águilas consecutivas
En una secuencia de $n$ volados ¿cuántos resultados no tienen dos águilas consecutivas, excepto al final?
Solución
Sea $u_n$ el número buscado. Los resultados, ya sea inician con águila (A) o bien con sello (S). Si inician con águila son $u_{n-2}$; si con sello, son $u_{n-1}$. Por tanto, $u_n=u_{n-1}+u_{n-2}$
Los saluda
jmd
PD: Comentarios después