Recursividad, palabras de código y conjuntos de

Question

"Un código-palabra del alfabeto $\{0,1,2\}$ es considerada legítima, si y sólo si no hay dos $0$'s aparecen de forma consecutiva. Encontrar una recurrencia para el número de $b_n$ de código legítimo-palabras".

Mi tonto solución para esto es la observación de que, dado el código-las palabras de la longitud de uno (hay tres de ellos), se puede añadir cualquiera de las $\{0,1,2\}$ encontrar $b_2$, a partir de la resultante $9$ código de dos letras de la palabra sólo $8$ son válidos (no consecutivos 00) o $ 3 \times 3 - 1 = 8$.

Para encontrar $b_3$ trabajamos de una manera similar, anexando 1,2 o 3 nos dan 24 código de palabras, pero sólo 22 de ellos son válidos: $3\times8 - 2 = 22$. La siguiente iteración es: $3\times22-6=3\times22-2\times3=60$,$3\times60-16=3\times60-2\times8=164$.

Poniendo todo esto junto (en papel) y te darás cuenta de que, en general, parece que $b_n=3\times b_{n-1}-2\times b_{n-3}$. Que parece la solución correcta.

Este problema puede ser resuelto también por el uso de algunos de teoría de conjuntos metodologías, ¿alguien tiene alguna idea de cómo puede hacerse esto? Esto debe ser algo similar a la prueba de que, dado un conjunto $A_n$ donde$a_i=\{0,1\}$, entonces el número de subconjuntos de a $A$ que no tienen consecutivos 0 es: $b_n=F_{n+1}$ $n\ge1$ donde $F_n$ es el n-ésimo número de Fibonacci.

Answer 1

Supongamos que $A=\{0,1,2,\cdots,r\}$ ser un conjunto de duración $r+1$. Queremos contar a todos los sub-secuencias de longitud $n$ del conjunto de $A$ tal que no hay dos cero consecutivos en estas sub-secuencias. Deje que el número de estos sub-secuencias que se denota con a $Z_r(n)$.

Si la primera posición de la $n$-matriz de los números $\{1,2,\cdots ,r\}$ el otro $n-1$ posición puede ser llenado por $Z_r(n-1)$ de los casos. En continuar, Si la primera posición de la $n$-matriz cero, a continuación, la segunda posición deben ser los números de $\{1,2,\cdots ,r\}$ y el otro $n-2$ posición puede ser llenado por $Z_r(n-2)$ de los casos.

El deseado sub-secuencias de longitud $n$ comienzan con cero o $\{1,2,\cdots ,r\}$ y los dos casos mencionados están separados y cubrir todos estos sub-secuencias. De manera que el término de $Z_r(n)$ puede ser definido de la siguiente manera $$ Z_r(n)=r\, Z_r(n-1)+r\, Z_r(n-2) $$ Los dos primeros valores iniciales de $Z_r(n)$ son definidos de la siguiente forma:

$ Z_r(0)=1$ porque no es sólo de número cero.

$ Z_r(1)=r+1$ porque no se $r+1$ números de longitud $1$

En su pregunta,$r=2$, y el de la secuencia es la siguiente : $$ \begin{array}{ccccc} Z_2(n)=2\, Z_2(n-1)+2\, Z_2(n-2) &,& Z_2(0)=1& ,&Z_2(1)=3 \end{array} $$