Número de cadenas de bits

Question

Cuánta cadena de bits de longitud 28

• ¿tener por lo menos un 000 consecutivo?
• ¿Sin 000 consecutivos?

Estoy usando ti nspire, ¿puedo hacerlo con la función nCr.

He intentado hacerlo pero no he encontrado la manera.

Gracias.

he visto este post : Número de cadenas binarias de longitud 8 que contienen tres 0s consecutivos o cuatro 1s consecutivos

y este otro: http://www.techtud.com/doubt/combinatorics-how-many-bit-string-length-eight-contai

pero no me ayudó.

Answer 1

Dejemos que $a_n$ sea una cadena de bits de longitud n sin 000, entonces puede ser

$a_{(n-3)}$ con 100 añadidos al final,

o $a_{(n-2)}$ con 10 añadidos al final,

o $a_{(n-1)}$ con 1 añadido al final.

Así que $a_n = a_{(n-1)} +a_{(n-2)} + a_{(n-3)}$

empezando por $a_0 = 1, a_1=2, a_2 = 4$

---

El final de cualquier cadena exitosa se puede clasificar como 1 (111,101,011,001) 10 (110.010) o 100.

1 puede añadirse a cualquier cadena exitosa de longitud (n-1) sin importar el final.

10 puede añadirse a cualquier cadena exitosa de longitud (n-2) sin importar el final.

100 puede añadirse a cualquier cadena exitosa de longitud (n-3) sin importar el final.