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,…,n} de manera que no contenga números consecutivos?

Solución
Sea un el número de subconjuntos de {1,2,….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 un−2 --pues es el número de subconjuntos de {3,4,…,n}.

Por otro lado, si el subconjunto no contiene el 1, entonces el número de subconjuntos de esta clase son un−1 --dado que es el número de subconjuntos de {2,3,…,n}.

En resumen, un=un−1+un−2. (Claramente, u1=1,u2=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 un 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, u1=0,u2=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:

un=2n−2+un−2+un−1

con u1=0,u2=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 un el número de números que cumplen para n. Claramente, u1=1,u2=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 un−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 Un−2 --siguiendo un razonamiento similar. Por tanto un=un−1+un−2.
Otra forma: Considerando el último dígito, éste puede ser 1 o bien 2. Los números que terminan en 2 son un−2 y los que terminan en 1 son un−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 un−1 y los que empiezan con uno son un−2 --porque en realidad deben empezar con 10. Por tanto, un=un−1+un−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 un el número buscado. Los resultados, ya sea inician con águila (A) o bien con sello (S). Si inician con águila son un−2; si con sello, son un−1. Por tanto, un=un−1+un−2

Tomado de:

Mate Mat