¿Puede alguien ayudarme a encontrar la relación de recurrencia en combinatoria?

Question

Chicos, estoy teniendo problemas para encontrar una relación recurrente.

Una palabra clave se compone de los dígitos $0,1,2,3$ (¡el orden es importante!). Una palabra clave se define como legítima si y sólo si tiene un número par de $0$ 's. Sea $a_n$ sea el número de palabras clave legítimas de longitud $n$ . Escribe una recurrencia para $a_n$ .

La respuesta es $a_n = 3a_{n-1} + 4^{n-1} - a_{n-1}$

Sé dónde $a_n=3a_{n-1}$ pero el problema es que no puedo averiguar de dónde viene el descansa ( $4^{n-1} - a_{n-1}$ ).

Por favor, ¿alguien puede decirme cómo enfocar la cuestión?

Gracias.

Answer 1

Así que veamos una palabra $w = w_1 \ldots w_n$ de longitud $n$ con $w_i \in \{0,1,2,3\}$ y denotar por $w' = w_2 \ldots w_n$ la palabra que consiste en todo menos la primera letra. $w$ es legítimo en los siguientes casos:

• $w_1 \ne 0$ y $w'$ es legítimo (ya que entonces el número de $0$ s en $w$ es igual a la de $w'$ . Hay 3 posibilidades para $w_1$ y $a_{n-1}$ para $w'$ Por lo tanto $3a_{n-1}$ para $w$ de esta forma.

• $w_1 = 0$ y $w'$ es ilegítimo (ya que entonces el número de $0$ s en $w'$ tiene que ser impar) hay $4^{n-1}$ palabras de 4 letras con longitud $n-1$ de los cuales $a_{n-1}$ son legítimos, por lo tanto $4^{n-1}-a_{n-1}$ ilegítimo. Así que $4^{n-1}-a_{n-1}$ posibilidades de $w$ en este caso.

Answer 2

Puede utilizar funciones generadoras exponenciales (el orden es importante, los dígitos están etiquetados). Para los dígitos 1, 2, 3 no hay restricciones: $$ 1 + \frac{z}{1!} + \frac{z^2}{2!} + \ldots + \frac{z^n}{n!} + \ldots = e^z $$ Para el dígito 0 (sólo se permite el número par): $$ 1 + \frac{z^2}{2!} + \frac{z^4}{4!} + \ldots + \frac{z^{2 n}}{(2 n)!} + \ldots = \frac{e^z + e^{-z}}{2} $$ Para las palabras clave completas: $$ (e^z)^3 \cdot \frac{e^z + e^{-z}}{2} = \frac{e^{4 z} + e^{2 z}}{2} $$ El coeficiente de $\frac{z^n}{n!}$ en esto se ve: $$ \frac{4^n + 2^n}{2} $$

Answer 3

Puede empezar a definir $a_n$ como el número de palabras legítimas de longitud $n$ y $b_n$ el ilegítimo de la longitud $n$ . Claramente $a_n + b_n = 4^n$ . También $a_0 = 1$ , $b_0 = 0$ .

Para obtener una palabra legítima de longitud $n + 1$ puede comenzar con una legítima de longitud $n$ y añadir uno de 3 dígitos, o empezar con un uno ilegítimo y añadir un cero (una opción): $$ a_{n + 1} = 3 a_n + b_n $$ Para obtener un ilegítimo, a partir de un legítimo añada un cero (una vía) o un ilegítimo añada uno de 3 dígitos: $$ b_{n + 1} = a_n + 3 b_n $$ Pero ya hemos terminado, teníamos $b_n = 4^n - a_n$ anterior, sustituyendo esto en la recurrencia para $a_n$ : $$ a_{n + 1} = 3 a_n + 4^n - a_n = 2 a_n + 4^n \qquad a_0 = 1 $$ También se podría decir: \begin {align} a_{n + 2} &= 3 a_{n + 1} + b_{n + 1} \\ &= 3 a_{n + 1} + (a_n + 3 b_n) \\ &= 3 a_{n + 1} + a_n + 3 (a_{n + 1} - 3 a_n) \\ &= 6 a_{n + 1} - 8 a_n \end {align} Para las condiciones iniciales, $a_0 = 1$ y $a_1 = 3 a_0 + b_0 = 3$