Encontrar una definición recursiva de esta secuencia

Question

Siempre tengo alguna dificultad con problemas de este tipo, y me preguntaba si no era un típico truco que hace que sea razonable.

Deje $W_n$ el número de palabras de longitud $n$ formado con las letras $A$ e $B$ tales que

• No hay palabras que contienen secuencias de $A$s con una longitud de exactamente 2

• No hay palabras que contienen secuencias de $B$s con una longitud de exactamente 2 o 3.

Ejemplos de palabras: $AAAB, ABABABA, ABBBBAAABA$, y de no-palabras: $AAB, ABBBA$, etc.

Estos "recursividad con restricciones" tipo de problemas siempre me causa dificultad. Quiero escribir $W_n = f(W_{n-1}, W_{n-2}, \ldots, W_{n-k})$ para algunos fijos $k$. Traté de romper en los casos basándose en lo que la última carta es, por lo $W_n = A_n + B_n$ donde $A_n$ es el número de palabras de longitud $n$ que terminan en $A$ e $B_n$ se define de manera similar. A continuación, obtener definiciones recursivas para $A_n$ en términos de $B_{n-k_i}$ e $W_{n-k_j}$ y de la misma manera definiciones recursivas para $B_n$ produce un lío de términos que no cancele incluso cuando recibe estos $W_{n-11}$ términos que aparecen. Seguramente me estoy perdiendo el truco?

Answer 1

Podemos escribir una recursividad infinita y, a continuación, simplificar.

Deje $A_n$ ser el número de secuencias que terminan en Ay $B_n$ ser el número de secuencias que terminan en B. Contamos la cadena vacía en ambos.

Entonces, para $n \ge 1$, tenemos $$ A_n = B_{n-1} + B_{n-3} + B_{n-4} + B_{n-5} + \dotsb $$ porque podemos agregar A o AAA o AAAA o AAAAA al final de una cadena que termina en B, pero no tanto. Así, por $n \ge 2$, tenemos \begin{align} A_n - A_{n-1} &= (B_{n-1} + B_{n-3} + B_{n-4} + B_{n-5} + \dotsb) - (B_{n-2} + B_{n-4} + B_{n-5} + B_{n-6} + \dotsb) \\ &= B_{n-1} - B_{n-2} + B_{n-3}. \\ A_n &= A_{n-1} + B_{n-1} - B_{n-2} + B_{n-3}. \end{align} Podemos hacer la misma cosa para $B_n$, salvo que $B_n$ no tienen un $A_{n-3}$ plazo en la recurrencia. Para $n\ge 2$, obtenemos \begin{align} B_n - B_{n-1} &= (A_{n-1} + A_{n-4} + A_{n-5} + \dotsb) - (A_{n-2} + A_{n-5} + A_{n-6} + \dotsb) \\ &= A_{n-1} - A_{n-2} + A_{n-4}. \\ B_n &= A_{n-1} + B_{n-1} - A_{n-2} + B_{n-4}. \end{align} Esto ya es suficiente para hacer que el problema de un número finito de recurrencia lineal, pero todavía podemos tratar de simplificarla.

---

Para $n \ge 1$, tenemos $W_n = A_n + B_n$, por lo que tenemos $$ W_n = 2W_{n-1} - W_{n-2} +B_{n-3} + A_{n-4} $$ sumando las dos ecuaciones. Por desgracia, todavía tenemos un mal $A$ e $B$ a tratar aquí.

La expansión de $B_{n-3}$ e $A_{n-4}$ usando sus recurrencias, obtenemos \begin{align} W_{n} &= 2W_{n-1} - W_{n-2} + (W_{n-4} - A_{n-5} + A_{n-7}) + (W_{n-5} - B_{n-6} + B_{n-7}) \\ &= 2W_{n-1} - W_{n-2} + W_{n-4} + W_{n-5} - A_{n-5} - B_{n-6} + W_{n-7} \end{align} lo que de nuevo tiene un no coinciden $A$ e $B$, pero ahora en el orden inverso. Así que si restamos $W_{n-2}$ desde ambos lados, obtenemos \begin{align} W_n - W_{n-2} &= (2W_{n-1} - W_{n-2} + W_{n-4} + W_{n-5} - A_{n-5} - B_{n-6} + W_{n-7}) \\&\quad - (2W_{n-3} - W_{n-4} + B_{n-5} + A_{n-6}) \\ &= 2W_{n-1} - W_{n-2} - 2W_{n-3} + 2W_{n-4} - W_{n-6} + W_{n-7} \end{align}

y el final de la recursividad es $W_n = 2W_{n-1} - 2W_{n-3} + 2 W_{n-4} - W_{n-6} + W_{n-7}$. (Esto no puede volar por pequeño $n$ - en particular, $W_0 \ne A_0 + B_0$ - , sino por $n> 7$ todas las manipulaciones anteriores son válidas.)

Answer 2

Quizás este gráfico será de ayuda:

Usted quiere contar los paseos de longitud <span class="math-container">$n$</span> a partir del estado de extremo izquierdo y termina en cualquiera de los Estados azules.

Answer 3

Deje $w(n)$ el número de clasificación de palabras de longitud $n$.

A continuación, $w$ satisface la recursividad $$w(n)=2w(n-1)-2w(n-3)+2w(n-4)-w(n-6)+w(n-7)$$ para $n\ge 8$, con valores iniciales \begin{align*} w(0)&=1\\ w(1)&=2\\ w(2)&=2\\ w(3)&=3\\ w(4)&=6\\ w(5)&=11\\ w(6)&=18\\ w(7)&=30\\ \end{align*} El por encima de la recursividad puede ser derivada de la siguiente manera . . .

Definir las funciones de $a_1,a_3,b_1,b_4$ por

• $a_1(n)$ es el número de clasificación de palabras de longitud n en la última constante bloque es exactamente "Una".
• $a_3(n)$ es el número de clasificación de palabras de longitud n en la última constante bloque termina con "AAA" (es decir, al menos $3$ apariciones consecutivas de "A").$\\[6pt]$
• $b_1(n)$ es el número de clasificación de palabras de longitud n en la última constante bloque es exactamente "B".
• $b_4(n)$ es el número de clasificación de palabras de longitud n en la última constante bloque termina con "BBBB" (es decir, al menos $4$ apariciones consecutivas de "B").

Entonces obtenemos la siguiente vinculado recursividad: \begin{align*} w(n)&= \begin{cases} 1\;\text{if}\;n=0\\ a_1(n)+a_3(n)+b_1(n)+b_4(n)\;\text{if}\;n > 0\tag{eq1}\\ \end{casos} \\[4pt] a_1(n)&= \begin{cases} 0\;\text{if}\;n<1\\ 1\;\text{if}\;n=1\\ b_1(n-1)+b_4(n-1)\;\text{if}\;n > 1\tag{eq2}\\ \end{casos} \\[4pt] a_3(n)&= \begin{cases} 0\;\text{if}\;n<3\\ 1\;\text{if}\;n=3\\ b_1(n - 3) + b_4(n - 3)+a_3(n-1)\;\text{if}\;n > 3\tag{eq3}\\ \end{casos} \\[4pt] b_1(n)&= \begin{cases} 0\;\text{if}\;n<1\\ 1\;\text{if}\;n=1\\ a_1(n-1)+a_3(n-1)\;\text{if}\;n > 1\tag{eq4}\\ \end{casos} \\[4pt] b_4(n)&= \begin{cases} 0\;\text{if}\;n<4\\ 1\;\text{if}\;n=4\\ a_1(n - 4) + a_3(n - 4)+b_4(n-1)\;\text{if}\;n > 4\tag{eq5}\\ \end{casos} \\[4pt] \end{align*} La aplicación de los enlaces de la recursividad, obtenemos \begin{align*} w(0)&=1\\ w(1)&=2\\ w(2)&=2\\ w(3)&=3\\ w(4)&=6\\ w(5)&=11\\ w(6)&=18\\ w(7)&=30\\ \end{align*} A continuación, nos desvincular los enlaces de la recursividad . . .

El uso de $(\text{eq}2)$, podemos eliminar el $a_1$.

A continuación, el uso de $(\text{eq}4)$, podemos eliminar el $b_1$.

A continuación, el uso de $(\text{eq}5)$, podemos eliminar el $a_3$.

Basado en las eliminatorias, de $(\text{eq}1)$ tenemos $$ w(n)=2b_4(n+3)-4b_4(n+1)+3b_4(n)+2b_4(n-1)-3b_4(n-2)+b(n-3)+b(n-4)-b_4(n-5) $$ para $n\ge 6$, y de $(\text{eq}3)$ tenemos $$ b_4(n)=2b_4(n-1)-2b_4(n-3)+2b_4(n-4)-b_4(n-6)+b_4(n-7) $$ para $n\ge 8$.

Desde cambios de $b$ satisfacer la misma recursividad como $b$, y desde $w$ es una combinación lineal de $b$ y los cambios de $b$, se deduce que el $w$ también satisface la misma recursividad como $b$, por lo tanto tenemos $$w(n)=2w(n-1)-2w(n-3)+2w(n-4)-w(n-6)+w(n-7)\tag{eq6}$$ para $n\ge 13$.

Ya tenemos los valores de $w(n)$ para $0\le n\le 7$.

La aplicación de los enlaces de la recursividad, podemos obtener los valores de $w(n)$ para $8\le n\le 12$, y se puede comprobar que en $(\text{eq}6)$ falla por $n=7$, pero se mantiene para $8\le n\le 12$, por lo tanto tiene para todos los $n\ge 8$.

Answer 4

Aquí es una reescritura de trabajo por encima de el uso de los autómatas, y la generación de funciones. El asociado gramáticas de la necesidad de ser ambigua; si no, a causa de las copias, el número obtenido será más alto que el derecho.

En el segundo diagrama, se puede escribir

$A = x + xC + xD$ donde :

$A = a_1x + a_2x^2 + a_3x^3 + ... $es la generación de la función (o el índice de cadena) para las palabras que termina exactamente en $0$. Hemos expresiones similares para B, C y D.

Del mismo modo, las otras tres ecuaciones son:

$B = x^3 + xB + x^3C + x^3D $

$C = x + xA + xB$

$D = x^4 + x^4A + x^4B + xD$

Aquí $x$ stands para $0$ o $1$, $x^3$ cubre la cadena de bits $000$; $x^4$ cubre la cadena de bits $1111$;

La de arriba (segundo) sistema soluciona fácilmente a la misma solución que el primer diagrama :

aquí (por ejemplo), $x + {x^3 \over 1-x } $ codifica el conjunto { 0, 000, 0000, 00000, ....}

las dos ecuaciones son

$ A+B = {x-x^2+x^3 \over 1-x } ( C + D + 1 ) $ y

$ C+D = {x-x^2+x^4 \over 1-x } ( A + B + 1 ) $

que soluciona fácilmente a $ W=A+B+C+D= {2x - 2x^2 - x^3 + 4x^4 -x^5 -2x^6 + 2x^7 \over 1 - 2x + 2x^3 - 2x^4 + x^6 - x^7} $

$= 2+2x +3x^2 +6x^3 +11x^4 +18x^5+30x^6 +50x^7 +85x^8 +143x^9+ 241x^{10} + ...$

El denominador codifica la necesaria recurrencia.