Combinaciones (secuencia de recuento) de palabras

Question

He estado trabajando en estos dos problemas de práctica, no estoy muy seguro de si mis soluciones son correctas o no.

1. ¿Cuál es la secuencia de recuento de todas las palabras del $\{a, b, c\}$ que contengan exactamente un $a$ ?

   Para esta pregunta he llegado a la conclusión de que la secuencia es $\binom{n}{1}\cdot2^{n-1}$

2. Tenemos $\{a, b\}$ no se permiten "b" consecutivas.

   ¿Cómo comienza la secuencia de recuento (al menos hasta el tamaño $6$ )?

Creo que debería adoptar el enfoque de la combinación sin repetición, pero no tengo ni idea de por dónde empezar.

Se agradecería una guía paso a paso para este problema.

Answer 1

Para la segunda parte $c_n$ denotan el número de $n$ palabras de letras que satisfacen sus restricciones. Deje que $w=l_1l_2\dots l_n$ sea una palabra de este tipo, donde $l_i\in\{a,b\}$ para $1\leq i\leq n$ . Si $l_1=a$ entonces esto no induce ninguna restricción en las letras restantes $l_2\dots l_n$ . Esto significa que $l_2\dots l_n$ es una palabra de longitud $n-1$ que cumplan los requisitos de repetición, es decir, que haya exactamente $c_{n-1}$ palabras de longitud $n$ que cumplan las normas y cuya primera letra sea $a$ . Ahora bien $l_1=b$ debemos tener que $l_2=a$ de lo contrario tendríamos dos $b$ 's. Una vez colocado el $a$ no hay otros efectos que $l_1$ tiene sobre el resto de su palabra. Esto significa que $l_3\dots l_n$ es una palabra de longitud $n-2$ satisfacer sus necesidades. Así que hay $c_{n-2}$ palabras de longitud $n$ que no tienen consecutivos $b$ y cuya primera letra es una $b$ . Como cada palabra sólo puede empezar por $a$ o $b$ Hemos agotado todas las posibilidades. Así tenemos la recurrencia $$ c_n=c_{n-1}+c_{n-2}, $$ con las condiciones iniciales obvias $c_1=2$ dada por las palabras $a$ y $b$ y $c_2=3$ dada por las palabras $aa$ , $ab$ y $ba$ . ¿Puedes irte de aquí?