Número de secuencias de longitud $m$ tal que $1$ nunca va seguido inmediatamente de $0$

Question

Hallar el número de secuencias de longitud $m$ formado sólo por dígitos, donde cada dígito está en $\{0,1,2\}$ y tal que $1$ nunca va seguido inmediatamente de $0$ .

Intento: Intenté tomar 10 como bloque, pero no llegué a ninguna parte. Encontré el Matemáticas pregunta Número de permutaciones del conjunto thet $\{1,2,...,n\}$ en el que $k$ nunca va seguido inmediatamente de $k+1$ .

Usando eso, como necesito eliminar sólo 1 seguido de 0, obtengo sólo un conjunto $A_1$ Así que.., $3^m$ - 6 (3*2). Elija el otro número de tres maneras, y podemos permutar 10 y otro número de dos maneras). ¿Es correcto? No tengo conocimientos de matemáticas; por favor, tenlo en cuenta si es posible.

Answer 1

Podemos considerar una cadena de Markov con tres estados $\{0,1,2\}$ correspondiente al último carácter analizado. La matriz de adyacencia de una cadena de Markov de este tipo es $$ P=\begin{pmatrix}1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1\end{pmatrix} $$ (por lo que sólo la transición $0\mapsto 1$ no está permitido) y el número $S_m$ de cadenas de $m\geq 1$ caracteres con la propiedad dada es la suma de los elementos de $P^{m-1}$ . Ahora puede calcular $S_m$ a partir de una descomposición espectral de $P$ . La forma combinatoria habitual es considerar que cualquier cadena válida con longitud $m$ sólo puede comenzar con un prefijo entre $$ 1,\quad 2,\quad 02,\quad 002,\quad 0002,\quad \ldots,\quad 000\ldots000.$$ De ello se deduce que, fijando $S_0=1$ , $$ S_m = 2 S_{m-1} + S_{m-2} + S_{m-3} + \ldots + S_{0} $$ $$ S_{m+1} = 2 S_{m} + S_{m-1} + S_{m-2} + \ldots + S_{0} $$ $$ S_{m+1}-S_{m} = 2S_m-2S_{m-1}+S_{m-1} $$ y $$ S_{m+1} = 3S_{m}-S_{m-1},\quad S_0=1, S_1=3 $$ así que $$\boxed{ S_m = \frac{1}{\sqrt{5}}\left[\left(\frac{3+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{3-\sqrt{5}}{2}\right)^{n+1}\right]=\color{red}{F_{2n+2}} }$$ el número de nuestras cadenas viene dado por un número de Fibonacci. Una biyección combinatoria que muestra lo mismo puede ser la siguiente: si mapeamos $0\mapsto 01$ , $1\mapsto 10$ , $2\mapsto 00$ las cadenas válidas de longitud $n$ se convierten en cadenas binarias de longitud $2n$ con la propiedad de que dos " $1$ s" nunca están uno al lado del otro. Por ejemplo: $$ 021002 \mapsto 010010010100 $$ y este último es un problema famoso.

Answer 2

SUGERENCIA: Llame a dicha secuencia bien y que $a_n$ sea el número de secuencias buenas de longitud $n$ . Si $\sigma$ es una buena secuencia de longitud $n$ podemos formar $3a_n$ secuencias de longitud $n+1$ añadiendo un $0,1$ o $2$ hasta el final de $\sigma$ . Toda secuencia buena de longitud $n+1$ pueden obtenerse de este modo, pero lamentablemente también algunas malas. Las malas son las que terminan en $10$ . Se obtienen claramente añadiendo $01$ a una buena secuencia de longitud $n-1$ y hay $a_{n-1}$ de esos, por lo que nuestro recuento de $3a_n$ incluye exactamente $a_{n-1}$ secuencias malas, y encontramos que $a_{n+1}=3a_n-a_{n-1}$ o

$$a_n=3a_{n-1}-a_{n-2}\tag{1}$$

con valores iniciales $a_0=1$ (porque la secuencia vacía es buena) y $a_1=3$ .

Ahora utiliza tu método favorito para resolver la recurrencia $(1)$ para obtener una forma cerrada de $a_n$ .

Un atajo: Si calcula los primeros $a_n$ se obtiene la siguiente tabla:

$$\begin{array}{rcc} n:&0&1&2&3&4&5&6\\ a_n:&1&3&8&21&55&144&377 \end{array}$$

Si reconoces la fila inferior como una subsecuencia de alguna secuencia familiar, puedes ser capaz de probar que realmente es esa subsecuencia y usarla para obtener una forma cerrada más fácilmente.

Añadido: Desde Jack D'Aurizio ha mencionado ahora explícitamente los números de Fibonacci, me extenderé en la parte del atajo. Es bastante conocido (y fácil de demostrar) que el número de maneras de embaldosar un $1\times n$ tira usando $1\times 1$ y $1\times 2$ fichas (monominós y dominós) es $F_{n+1}$ . Por lo tanto, hay $F_{2n+2}$ formas de embaldosar una tira de longitud $2n+1$ . Numerar las casillas de la tira $1$ a través de $2n+1$ de izquierda a derecha, y supongamos que tenemos un embaldosado de la tira por monominós y dominós. Etiquetar cada celda par $L$ si está cubierto por la mitad izquierda de una ficha de dominó, $R$ si está cubierta por la mitad derecha de una ficha de dominó, y $S$ si está cubierto por un monomino. Hay $n$ células pares, por lo que este etiquetado produce una cadena de longitud $n$ sobre el alfabeto $\{L,R,S\}$ . La única restricción para estas cadenas es que no pueden contener la subcadena $LR$ (¿por qué?). Así, hay $F_{2n+2}$ cadenas de longitud $n$ sobre el alfabeto $\{L,R,S\}$ en el que $L$ nunca va seguido de $R$ . Sustituir $L,R$ y $S$ por $1,0$ y $2$ respectivamente, para asignar estas cadenas a las del problema.

Answer 3

Para variar, dejemos que $A_n$ el número de secuencias de longitud $n$ que terminan en $1$ .

Sea $B_n$ el número de secuencias de longitud $n$ que no terminan en $1$ .

Entonces,

• $A_0 = 0$
• $B_0 = 1$
• $A_{n+1} = A_n + B_n$
• $B_{n+1} = A_n + 2 B_n$

Puedes utilizar tu método favorito para resolver esta relación de recurrencia.

(frases para seguir buscando: "recurrencia lineal", "ecuación en diferencias")

Answer 4

Esta respuesta se basa en la Método de agrupación de Goulden-Jackson .

Consideramos el conjunto de palabras de longitud $m\geq 0$ construido a partir de un alfabeto $$\mathcal{V}=\{0,1,2\}$$ y el conjunto $B=\{10\}$ de malas palabras que no pueden formar parte de las palabras que buscamos. Derivamos una función generadora $f(s)$ con el coeficiente de $s^m$ el número de palabras buscadas de longitud $m$ .

Según el documento (p.7) la función generadora $f(s)$ es \begin{align*} f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1} \end{align*} con $d=|\mathcal{V}|=3$ el tamaño del alfabeto y $\mathcal{C}$ el peso-numerador de malas palabras con \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[10]) \end{align*} Calculamos según el documento \begin{align*} \text{weight}(\mathcal{C}[10])&=-s^2\\ \end{align*}

y obtener

\begin{align*} f(s)&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-3s+s^2}\\ \end{align*}

Descomposición de fracciones parciales y expansión de $f(s)$ resulta en

\begin{align*} f(s)&=\frac{3+\sqrt{5}}{2\sqrt{5}}\cdot\frac{1}{1-\frac{3+\sqrt{5}}{2\sqrt{5}}s} -\frac{3-\sqrt{5}}{2\sqrt{5}}\cdot\frac{1}{1-\frac{3-\sqrt{5}}{2\sqrt{5}}s}\\ &\\ &=\frac{1}{\sqrt{5}}\sum_{m=0}^{\infty}\left[\left(\frac{3+\sqrt{5}}{2}\right)^{m+1}-\left(\frac{3-\sqrt{5}}{2}\right)^{m+1}\right]s^m\\ \\ &=1+3s+8s^2+21s^3+\color{blue}{55}s^4+144s^5+377s^6+\cdots \end{align*} con el coeficiente de $s^m$ que da el número de palabras válidas de longitud $m$ .

El número de palabras válidas de longitud $4$ es $55$ . Aquí tiene una lista con todos los $4^3=81$ palabras y la $26$ palabras no válidas marcadas en azul.

\begin{array}{ccccccccc} 0000&0\color{blue}{10}0&0200&\color{blue}{10}00&1\color{blue}{10}0&1200&2000&2\color{blue}{10}0&2200\\ 0001&0\color{blue}{10}1&0201&\color{blue}{10}01&1\color{blue}{10}1&1201&2001&2\color{blue}{10}1&2201\\ 0002&0\color{blue}{10}2&0202&\color{blue}{10}02&1\color{blue}{10}2&1202&2002&2\color{blue}{10}2&2202\\ 00\color{blue}{10}&01\color{blue}{10}&02\color{blue}{10}&\color{blue}{10}\color{blue}{10}&11\color{blue}{10}&12\color{blue}{10}&20\color{blue}{10}&21\color{blue}{10}&22\color{blue}{10}\\ 0011&0111&0211&\color{blue}{10}11&1111&1211&2011&2111&2211\\ 0012&0112&0212&\color{blue}{10}12&1112&1212&2012&2112&2212\\ 0020&0120&0220&\color{blue}{10}20&1120&1220&2020&2120&2220\\ 0021&0121&0221&\color{blue}{10}21&1121&1221&2021&2121&2221\\ 0022&0122&0222&\color{blue}{10}22&1122&1222&2022&2122&2222\\ \end{array}