Relación de Recurrencia Deberes Pregunta 3

Question

Esta es una pregunta de HW

Considere el conjunto $T={A,B,C,1,2,3,4}$ . Para $ n \geq 0$ deja $c_n$ ser el número de secuencias de n caracteres de elementos de T que no contienen letras consecutivas (distintas o idénticas)

Creo que tiene que haber dos casos aquí. Por ejemplo Uno en el que $a_{10}$ termina en una carta, entonces $a_{11}$ tiene 4 opciones para el 11º dígito ${1,2,3 or 4}$ si no, si $a_{10}$ termina con un número, entonces podemos elegir cualquier elemento del conjunto T para el 11º personaje en $a_{11}$

¿Es mi comprensión de la pregunta correcta? Si lo es, podría darme una pista de cómo proceder.

Answer 1

Sí, su comprensión es correcta. Una forma de proceder es introducir una segunda variable: dejar $a_n$ ser el número de secuencias de longitud permitidas $n$ que terminan en un dígito. Luego $a_{n+1}=4c_n$ ya que siempre puedes añadir cualquiera de $4$ dígitos a un permitido $n$ - una cadena de caracteres.

PISTA: Expreso $c_{n+1}$ en la forma $kc_n+ \ell a_n$ para algunos números enteros positivos $k$ y $ \ell $ que no dependen de $n$ y utilizar la relación $a_n=4c_{n-1}$ para eliminar $a_n$ .

Answer 2

Llama a una palabra bueno si no tiene dos letras consecutivas. Deje que $c_n$ ser el número de buenas palabras de longitud $n$ .

Contamos el número de buenas palabras de longitud $n+1$ .

Son de dos tipos, i) los que terminan con un dígito y ii) los que terminan con una letra.

(i) Hay como usted vio $4c_n$ buenas palabras de longitud $n+1$ que terminan con un dígito. Porque podemos añadir cualquier dígito a una buena palabra de longitud $n$ .

ii) ¿Qué hay de las buenas palabras de longitud $n+1$ que terminan con una carta? El $n$ -el símbolo de la cuarta (si hay una) debe ser un dígito, y la cadena de longitud $n-1$ antes de que eso pueda ser una buena cuerda. Así que escribe (ii) palabras de longitud $n+1$ se hacen tomando una buena palabra de longitud $n-1$ y añadiendo un dígito y luego una letra. Esto se puede hacer en $12$ maneras. Así que hay $12c_{n-1}$ Tipo ii) buenas palabras de longitud $n+1$ .

Ahora se puede escribir una bonita recurrencia lineal para $c_{n+1}$ en términos de $c_n$ y $c_{n-1}$ .

Observación: Una mejor manera de resolver el problema es dejar que $a_n$ ser el número de cuerdas buenas que terminan con un dígito, y $b_n$ el número de buenas cuerdas que terminan con una letra. Uno se vuelve muy natural $2$ -variables recurrencias. El análisis más limpio utiliza entonces matrices.