¿Cuál es el número de serie de más de $\{0,1,2\}$ con una longitud de $n$ sin repetir el mismo número uno después de otro ($22$ no está permitido, pero de $101$ es), que no empieza y termina con el número de $2$.
La serie $10210$ es bueno. La serie $2002$ no es bueno porque hay dos consecutivas $0$, y comienza y termina con $2$.
Traté de recurrencia con la siguiente fórmula:
$a_n=2a_{n-2}+a_{n-1}$
La razón es que el elemento antes de que el último ha $2$ opciones de acuerdo a su elemento anterior. Pero cuando pensaba en el último elemento pensé que puede ser 1 o 0 según el elemento antes de que.
Pero si $2$ es el elemento antes de la última creo que la fórmula no es correcta.
Debo dividir a los casos (otra fórmula $b_n$)?
Respuesta
¿Demasiados anuncios?
Considere el problema, pero con la condición de que el primer y el último número es siempre un $2$. Esto se corresponde con el problema original por acortamiento de la $2$s:
$$2\underbrace{010120}_{\text{original}}2$$
Deje $a_n$ el número de secuencias de longitud $n$. A continuación, $a_3 = 2$ es el primer cero de la entrada.
Ahora obviar que el último segundo número no puede ser un $2$, es manifiesto que la posición de cada uno $2 \ldots n-1$ $2$ opciones, contabilidad para $2^{n-2}$ posibilidades.
Pero observe que las secuencias con un $2$ en la posición $n-1$ corresponden bijectively a las que constituyen $a_{n-1}$:
$$\underbrace{21021212}_{\text{in $a_{n-1}$}}2$$
Así obtenemos la recurrencia:
$$a_n = 2^{n-2} - a_{n-1}$$
que es fácilmente resuelto mediante técnicas estándar.
