Número de cuerdas de longitud n formadas por $\{0,1,2\}$ de tal manera que $1$ y $2$ no se producen sucesivamente.

Question

¿Cuál es el número de formas de formar una cadena de longitudes $n$ del set $\{0,1,2\}$ de tal manera que $1$ y $2$ no se producen sucesivamente.

Answer 1

Deje que $A_n,B_n,C_n$ sea el número de tales cuerdas de longitud $n$ terminando en $0$ , $1$ y $2$ respectivamente. Estamos buscando $f(n)=A_n+B_n+C_n$ . Claramente $A_1=B_1=C_1=1$ . Tenemos las recurrencias $B_{n+1}=A_n+C_n$ , $C_{n+1}=A_n+B_n$ y $A_{n+1}=A_n+B_n+C_n$ . Por simetría $B_n=C_n$ para que esto se simplifique a $$ \left ( \begin {matrix}A_{n+1} \\B_ {n+1} \end {matrix} \right )= \left ( \begin {matrix}1&2 \\1 &1 \end {matrix} \right ) \left ( \begin {matrix}A_{n} \\B_ {n} \end {matrix} \right ).$$ La matriz tiene valores propios $1 \pm\sqrt 2$ de modo que la expresión para $A_n$ , $B_n$ y de hecho también por la cantidad $f(n)=A_n+2B_n$ necesario al final tiene la forma $$ f(n) = \alpha\left ({1+ \sqrt 2} \right )^n+ \beta\left (1- \sqrt 2 \right )^n.$$ Los números $ \alpha , \beta $ se obtienen de $ \alpha + \beta =f(0)=1$ y $( \alpha + \beta )+ \sqrt2 ( \alpha - \beta )=f(1)=3$ como $ \alpha = \frac {1+ \sqrt 2}2$ y $ \beta = \frac {1- \sqrt 2}2$ de modo que, en última instancia $$ f(n) = \frac12\left ( \left (1+ \sqrt 2 \right )^{n+1}+ \left (1- \sqrt 2 \right )^{n+1} \right ).$$

Answer 2

Lo resolveré usando relaciones de recurrencia. El truco está en formular las relaciones de recurrencia.

Una cuerda se llama buena si 1,2 no se producen sucesivamente. Que $a(n),b(n),c(n)$ ser el número de buenas cuerdas de longitud $n$ que terminan en $0,1,2$ respectivamente. Por cada buena cuerda de longitud $n$ que termina en $1$ o $2$ añadiendo $0$ a ella hará una buena cadena de longitud $n+1$ que termina en $0$ . De eso se deduce: $$a(n+1)=a(n)+b(n)+c(n)$$ De manera similar (Aquí cuidado que $1,2$ no pueden ser consecutivas): $$b(n+1)=a(n)+b(n)$$ $$c(n+1)=a(n)+c(n)$$

El número que le interesa es $a(n)+b(n)+c(n)$

Answer 3

Usemos las funciones de generación ( La "generación-functinología" de Wilf explica la técnica) para resolver esto. Llama a $a_n$ , $b_n$ , $c_n$ el número de cuerdas de longitud $n$ terminando en 0, 1, 2 respectivamente. Al considerar las formas de obtener cuerdas de longitud $n + 1$ añadiendo un dígito a las secuencias de longitud $n$ esto lleva a las recurrencias (recuerde que hay que tener cuidado de no llegar a los adyacentes 1, 2): $$ a_{n + 1} = a_n + b_n + c_n \\ b_{n + 1} = a_n + b_n \\ c_{n + 1} = a_n + c_n $$ También, $a_0 = b_0 = c_0 = 1$ . Estamos interesados en $f(n) = a_n + b_n + c_n = a_{n + 1}$ . Definir las funciones generadoras ordinarias: $$ A(z) = \sum_ {n \ge 0} a_n z^n \\ B(z) = \sum_ {n \ge 0} b_n z^n \\ C(z) = \sum_ {n \ge 0} c_n z^n $$ Por las propiedades de las funciones generadoras ordinarias: $$ \frac {A(z) - a_0}{z} = A(z) + B(z) + C(z) \\ \frac {B(z) - b_0}{z} = A(z) + B(z) \\ \frac {C(z) - c_0}{z} = A(z) + C(z) $$ Tu manso paquete de álgebra computacional resuelve este sistema de ecuaciones: $$ A(z) = \frac {1 + z}{1 - 2 z - z^2} \\ B(z) = C(z) = \frac {1}{1 - 2 z - z^2} $$ Estamos interesados en $a_{n + 1}$ : $$ A(z) = \frac {1}{2 (1 + \sqrt {2})} \cdot \frac {1}{1 - (1 + \sqrt {2})^{-1} z} + \frac {1}{2 (1 - \sqrt {2})} \cdot \frac {1}{1 - (1 - \sqrt {2})^{-1} z} $$ Esto da: $$ a_n = \frac {(1 + \sqrt {2})^{n - 1}}{2} + \frac {(1 - \sqrt {2})^{n - 1}}{2} $$ La respuesta final es que sí: $$ f(n) = a_{n + 1} = \frac {(1 + \sqrt {2})^n}{2} + \frac {(1 - \sqrt {2})^n}{2} $$ cuerdas en total de longitud $n$ .

Answer 4

Existe un interesante problema relacionado que tiene una solución mediante la inclusión-exclusión. Se trata de la restricción de las palabras inadmisibles a palabras en las que $1$ y $2$ ocurren en orden. Esto requiere que contemos el número de $n$ -cadenas que tienen $k$ casos de $1$ seguido de $2$ ocurriendo sucesivamente con $1 \le k \le \lfloor n/2 \rfloor $ . Este conteo puede hacerse considerando la longitud de los posibles huecos entre estos pares, que vienen dados por la función generadora $$ \left ( \frac {1}{1-z} \right )^{k+1}.$$ El total de estas lagunas debe ser igual a $n-2k$ dando $$[z^{n-2k}] \left ( \frac {1}{1-z} \right )^{k+1} = {n-2k+k \choose n-2k} = {n-2k+k \choose k} = {n-k \choose k}.$$ Por lo tanto, mediante inclusión-exclusión el número de cuerdas de longitud $n$ que contiene por lo menos una ocurrencia de $1$ y $2$ en el orden está dada por $$ \sum_ {k=1}^{ \lfloor n/2 \rfloor } (-1)^{k+1} {n-k \choose k} 3^{n-2k}$$ y el recuento donde $1$ y $2$ no se producen sucesivamente es $$3^n + \sum_ {k=1}^{ \lfloor n/2 \rfloor } (-1)^k {n-k \choose k} 3^{n-2k} = \sum_ {k=0}^{ \lfloor n/2 \rfloor } (-1)^k {n-k \choose k} 3^{n-2k}.$$ Si calculamos esto para valores pequeños obtenemos la secuencia $$1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765, 17711, 46368, 121393, 317811, 832040, \ldots $$ que es A001906 de la OEIS . Llama a esta secuencia $\{a_n\}$ . La función generadora ordinaria de esta secuencia viene dada por $$f(z) = \sum_ {n \ge 0} \sum_ {k=0}^{ \lfloor n/2 \rfloor } (-1)^k {n-k \choose k} 3^{n-2k} z^n.$$ Reordenando la suma encontramos que $$f(z) = \sum_ {k \ge 0} \sum_ { \lfloor n/2 \rfloor\ge k} (-1)^k {n-k \choose k} 3^{n-2k} z^n = \sum_ {k \ge 0} (-1)^k \times 3^{-2k} \sum_ { \lfloor n/2 \rfloor\ge k}{n-k \choose k} 3^n z^n .$$ La suma interna puede ser manipulada de la siguiente manera: $$ \sum_ {n \ge 2k} {n-k \choose k} 3^n z^n = \sum_ {n \ge 0} {n+2k-k \choose k} 3^{n+2k} z^{n+2k} = 3^{2k} z^{2k} \sum_ {n \ge 0} {n+k \choose k} 3^n z^n \\ = 3^{2k} z^{2k} \sum_ {n \ge 0} {n+k \choose n} 3^n z^n = 3^{2k} z^{2k} \left ( \frac {1}{1-3z} \right )^{k+1}.$$ Esto finalmente da para la función generadora que $$f(z) = \sum_ {k \ge 0} (-1)^k z^{2k} \left ( \frac {1}{1-3z} \right )^{k+1} = \frac {1}{1-3z} \sum_ {k \ge 0} (-1)^k z^{2k} \left ( \frac {1}{1-3z} \right )^k = \frac {1}{1-3z} \frac {1}{1+z^2/(1-3z)} = \frac {1}{1-3z+z^2}.$$ Los inversos de los polos de $f(z)$ están dadas por $$ \rho_ {0,1} = \frac {3 \pm\sqrt {5}}{2}$$ que conduce a la forma cerrada $$a_n = \frac {1}{ \sqrt {5}} \left ( \left ( \frac {3+ \sqrt {5}}{2} \right )^{n+1}- \left ( \frac {3- \sqrt {5}}{2} \right )^{n+1} \right ).$$