La recurrencia de la $\{0,1,2\}^n$ tuplas que no contengan $2$, seguido inmediatamente por $0$

Question

Yo estoy haciendo la parte (a) y la necesidad de algunos consejos con ella.

Mi método es dividir a los miembros de $\{t_n\}$ en 2 grupos:

$\bullet$ n-tuplas de inicio con $0$, es decir,$(0,\_ \ ,\_ \ ,\_ \ ,\_ \ ,\_ \ ,...)$: hay $t_{n-1}$ de las personas (es decir, que nos llene los espacios en blanco con los miembros de $\{t_{n-1}\}$).

$\bullet$ n-tuplas con $0$ en la posición $p$, para $p = 2,3,...,n-1$, $\ $ es decir,$(...,\_ \ ,\_ \ , 0,\_ \ ,\_ \ ,\_ \ ,...)$: queremos llenar los espacios en blanco con $\{t_{n-1}\}$, a excepción de aquellos que han $2$ en la posición $(p-1)$, $\ $e hay $t_{n-2}$ de las personas. Desde allí se $(n-2)$ posibles valores de $p$, el recuento ser $(n-2)(t_{n-1} - t_{n-2})$.

Me quedo pegado cuando es el momento de resumir lo anterior. Creo que se superponen, especialmente aquellos en la segunda viñeta, pero no puede decidir dónde.

==============================================

Edit: me he dado cuenta de que la división de los casos está mal, gracias a las respuestas de Henning Makholm y Hagen von Eitzen (y también el comentario de otro usuario, que por alguna razón se había ido). El primero de los conjuntos es bueno, pero el segundo no se complementan. Estoy pensando más acerca de este problema y editar mi pregunta de nuevo si es necesario.

Answer 1

Una idea mejor puede ser dejar a $a_n, b_n, c_n$ recuento de las cuerdas sin $2$, seguido por $0$ que comienzan con $0,1,2$, respectivamente. A continuación, tenga en cuenta que $$\begin{align} t_n&=a_n+b_n+c_n\\ a_n&=t_{n-1}\\ b_n&=t_{n-1}\\ c_n&=b_{n-1}+c_{n-1}\end{align}$$ y simplificar.

Answer 2

El primero de los conjuntos es un buen comienzo, pero ¿por qué no sus otros simplemente la validez $n$-tuplas que comienzan con $1$ o $2$?

Para extender una tupla de la primera clase, usted puede pegar un $0$ o $1$ frente a ella.

Para extender una tupla de la segunda clase, se puede pegar $0$, $1$, o $2$ frente a ella.

Esto le da un acoplado de primer orden de recurrencia entre el número de tuplas en cada uno de los conjuntos como $n$ aumenta.

Answer 3

Como señaló en un comentario, la recurrencia es $t_n=3t_{n-1}-t_{n-2}$, y hay una sencilla prueba de ello. Para elegir una cadena de longitud $n$,

1. Elija el último carácter [$3$ opciones].
2. Elegir la primera, $n-1$ personajes, de forma que no hay instancias de "$20$" aparecen [$t_{n-1}$ opciones].
3. Eliminar cualquier "mala" cadenas producidas por los dos primeros pasos que terminan en "$20$" [hay $t_{n-2}$ cadenas].

Luego, puede resolver que la recurrencia utilizando el método habitual, y luego darse cuenta de que coincide con la fórmula de Binet para $F_{2n+2}$.

---

Aquí es una prueba directa de que el número de cadenas que se da por $F_{2n+2}$. Nota: $F_{2n+2}$ es el número de maneras de baldosa una tira de unidad de plazas de longitud $2n+1$ con plazas y las fichas de dominó. Divida esta tira en $n$ consecutivos secciones de longitud dos, seguido por un final de la plaza. Hay tres opciones para cada sección:

(0) El derecho de la plaza está cubierta por la mitad derecha de una ficha de dominó.
(1) El derecho de la plaza está cubierta por un mosaico cuadrado.
(2) El derecho de la plaza está cubierta por la mitad izquierda de una ficha de dominó (que sobresale en la siguiente sección).

Resulta que estas opciones describe completamente el suelo de baldosas. Por ejemplo, aquí está el mosaico correspondiente a la cadena de $00122102$, donde X es un cuadrado y $<>$ es el de dos piezas de un dominó, mientras que la |s es la sección dividiers.

 0  0  1  1  2  2  1  0  2
<>|<>|XX|XX|X<|><|>X|<>|X<|>

Tenga en cuenta que el caso (2) no puede ser seguido por el caso (0), ya que las dos fichas de dominó necesariamente se superponen. Por lo tanto, el mosaico es descrito por una cadena de $n$ $0$s, $1$s y $2$s siguiendo las mismas restricciones que su problema.