Cinco problemas equivalentes al de Fibonacci

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