Número de secuencias de $0$s, $1$s y $2$s con longitud $n$ tal que hay un $0$ en alguna parte entre cada par de $2$s

Question

Deje $a(n)$ el número de secuencias con una longitud de $n$ que consiste en los dígitos $0,1,2$ de manera tal que entre cada dos apariciones de $2$ no es una ocurrencia de $0$ (no necesariamente junto a la $2$'s). Un ejemplo de buena secuencia es $0102102$. Un ejemplo de mala secuencia es $01212$.

A. Encontrar una fórmula de recursión para $a(n)$

B. Encontrar una expresión explícita para $a(n)$.

Yo: deje $x(n)$ el número de secuencias con una longitud de $n$ que si sumamos $2$ al final de la secuencia sigue siendo una buena secuencia con la longitud de la $n+1$.

Ahora, si el último dígito en la secuencia de se $0$, entonces tenemos que mirar en el número de secuencias con una longitud de $n-1$, por lo tanto $\displaystyle a(n-1)$.

Si el último dígito se $1$, entonces ahora tenemos que buscar en $x(n-1)$ y trabajar con la misma manipulación. De esta manera podemos obtener la recursividad $x(n)=a(n-1)+x(n-1)$. Por inducción puedo conseguir una fórmula de recursión para $x(n)$, pero no sé cómo encontrar una fórmula para $a(n)$ o encontrar una expresión explícita para $a(n)$.

Cualquier ayuda será apreciada, gracias!

Answer 1

$x(n) = x(n-1) + x(n-1) + \sum_{i=1}^{n-1}x(n-1 -i) + x(0), n\ge 2 $
$x(0)=1$ $, x(1)=3$.

Cualquier cadena válida comenzar con $0$ (número de tales cadenas se $x(n-1)$) o $1$ (número de tales cadenas se $x(n-1))$ o $2$.Si se inicia con $2$ debe tener sólo $1's$ antes de la primera aparición de $0$. Condición en la posición de la primera $0$ después de la $2$. Puede ser, o una $1$, seguido por $0$ etc y en el caso de que la aparición de $2$ es seguido por sólo $1's$ (número de tales cadenas se $x(0))$.

Editar

Más Simple Recurrencia

El uso de la repetición por encima de restar $x(n-1)$ $x(n)$ para obtener este simple recurrencia, $$x(n)= 3x(n-1)-x(n-2), n \ge 2 $$

Usted puede utilizar esta fórmula para calcular el cerrado fórmula fácilmente.

Answer 2

Considere lo siguiente: \begin{align*} r(n) &:= \text{number of sequences of 0s and 1s} = 2^n \\ s(n) &:= \text{number of sequences of 0s and 1s with at least one %#%#%} = 2^n - 1 \\ \end{align*} La correspondiente (ordinario) la generación de funciones \begin{align*} R(x) &= \sum_{n \ge 0} 2^n x^n = \frac{1}{1 - 2x} \\ S(x) &= \sum_{n \ge 0} (2^n - 1) x^n = \frac{1}{1 - 2x} - \frac{1}{1 - x} = \frac{x}{(1-2x)(1-x)}. \end{align*} La generación de la función $0$ $A(x)$ satisface, por el trabajo de casos en el número de $a(n)$ $k$s en la secuencia: \begin{align*} A(x) &= \underbrace{R(x)}_{k=0} + \underbrace{R(x) x R(x)}_{k=1} + \sum_{k \ge 2} R(x) (x S(x))^{k-1} x R(x) \\ &= R(x) + \sum_{k \ge 1} R(x)^2 S(x)^{k-1} x^{k} \\ &= R(x) + \frac{x R(x)^2}{1 - x S(x)} \\ &= \frac{1}{1 - 2x} + \frac{x / (1 - 2x)^2}{1 - \frac{x^2}{(1-x)(1-2x)}} \\ &= \frac{1}{1 - 2x} + \frac{x(1-x)}{(1-2x) \left[ (1-2x)(1-x) - x^2 \right]} \\ &= \frac{1 - 3x + x^2}{(1 - 2x)(1 - 3x + x^2)} + \frac{x - x^2}{(1-2x)(1 - 3x + x^2)} \\ &= \frac{1 - 2x}{(1 - 2x)(1 - 3x + x^2)} \\ &= \boxed{\frac{1}{1 - 3x + x^2}}. \end{align*}

---

Ahora que tenemos la generación de la función, nos damos cuenta de que $2$ satisface mucho más simple de recurrencia: $$ a(n) = 3(n-1) - a(n-2) $$ que se desprende directamente de $a(n)$. Esta recurrencia puede ser explicado de forma combinatoria así, y si le había molestado para ser un poco más inteligente de lo que podría haber encontrado la recurrencia en el primer lugar y guardar un poco de álgebra.

La conclusión, ya sea a partir de la repetición o de la búsqueda de los primeros valores en oeis que de hecho $$ a(n) = f(2n+2) $$ donde $A(x) (1 - 3x + x^2) = 1$ $f(k)$ésimo número de Fibonacci.

Answer 3

Deje $a(n)$ el número de aceptable cadenas de longitud $n$ que tienen un $2$ después de la última $0$. Deje $b(n)$ el número de aceptable cadenas de longitud $n$ que no tienen un $2$ después de la última cero. Usted tiene un par de recurrencias $a(n)=a(n-1)+b(n-1)$ debido a que para obtener uno puede anexar un $1$ $a$ o $2$ a un $b$. $b(n)=2b(n-1)+a(n-1)$ debido a que usted puede añadir un $0$ o $1$ $b$ o anexar una $0$$a$. Condiciones de partida son $a(1)=1, b(1)=2$ resulta de la $a$'s y $b$'s, alternan los números de Fibonacci.

Answer 4

Hola Galc127, hay 3 distintos casos que usted debe tener en cuenta.$$B_n=\{x\in \{0,1,2\}^n: x = r21^k ,r\in A_{n-k-1}\},$$is the set of good words that ends up with a $2$. $$C_n=\{x\in \{0,1,2\}^n: x = r2p0q ,r\in A_{n-k-2}\wedge pq\in \{0,1\}^k\},$$ Es el conjunto de buenas palabras, que termina con $2$$0$.
$$D_n=\{0,1\}^n,$$is the set that does not have any $2$'s.
Por lo tanto, $A_n=B_n\cup C_n\cup D_n$, y llame a $a_n=|A_n|,b_n=|B_n|,c_n=|C_n|,d_n=|D_n|$. Los conjuntos son disjuntos de modo $a_n=b_n+c_n+d_n$$d_n=2^n$.
Ahora, $$b_n=d_{n-1}+c_{n-1}+b_{n-1}=2^{n-1}+c_{n-1}+b_{n-1},$$$$c_n=2*c_{n-1}+b_{n-1}$$ ¿Por qué?(pruebe añadiendo caracteres apropiados al final de las cadenas en cada set)

La cosa con su trato de hacer es que usted no está usando $B_n$ cualquier lugar, su $x_n$ es como $d_n+c_n$.
Espero que ayude.
Editar: Como comentario, la generación de función sería la $$\frac{1}{1-2x}+\frac{x^2}{1-5x+7x^2-2x^3}+\frac{x}{1-3x+x^2}.$$

Answer 5

Deje $w$ ser arbitraria buena palabra de longitud $n$. Para extender $w$ a una buena palabra de longitud $n+1$,

tenemos 3 opciones para el último dígito. La palabra resultante siempre será bueno si el último dígito es 0 o 1,

así que tenemos que restar la cantidad de malas palabras que resultan cuando añadimos un 2:

Sea T el conjunto de las malas palabras de longitud $n+1$ que se convierten en un bien cuando el último dígito (2) se elimina, y

sea S el conjunto de las buenas palabras de longitud $n-1$;

vamos a mostrar a continuación que T y S tienen el mismo número de elementos, por lo que, a continuación,

$\hspace{.5 in}\color {red}{a(n+1)=3a(n)-a(n-1)}$.

---

$\textbf{1)} $Definir $f:T\rightarrow S$ mediante la eliminación de los dos últimos dígitos.

$\textbf{2)} $Definir $g:S\rightarrow T$ como sigue:

$\;\;\;\textbf{a)}$ Si $v$ termina en 0, deje $g(v)=v22$.

$\;\;\;\textbf{b)}$ Si $v$ termina en 2, deje $g(v)=v12$.

$\;\;\;\textbf{a)}$ Si $v$ termina en 1, vamos a $g(v)=\begin{cases}v22, &\mbox{if v has a 0 after the last 2 (if any)}\\ v12, &\mbox{if v does not have a 0 after the last 2} \end{cases}$

Desde $f$ $g$ son claramente inversos, S y T tienen el mismo número de elementos.