Número de palabras con dos letras$a$ y$b$.

Question

Dado$N$ y$M$, encuentre el número de$N$ palabras de letras que consisten solo en$a$ o$b$, donde$b$ no debe ser consecutivo para más que o igual a$M$ veces.

Ejemplo: si$N=3$ y$M=2$, entonces todas las palabras posibles son:$\{aaa , aab , aba , baa , bab\}$.

Answer 1

He aquí una idea.

Fix $M$, y deje $F_N$ denotar el número de palabras tal como usted la describe de la longitud de la $N$.

Una palabra de longitud $N$, se puede comenzar con un $a$ o $b$. Si empieza con un $a$, usted puede llenar el resto de la palabra en $F_{N-1}$ maneras. Si se comienza con un $b$... Bueno, si $M=2$, luego de la segunda carta tiene que ser un $a$, y esto te deja con $F_{N-2}$ maneras de llenar el resto de la palabra. Por lo tanto $F_N = F_{N-1} + F_{N-2}$, que yo también podría escribir como $F_N = F_{N-1} + \cdots F_{N-M}$.

Así que supongamos $M>2$, y que su palabra comienza con una $b$. A continuación, la segunda letra puede ser $a$ o $b$, y si es un $a$, se queda con $F_{N-2}$ maneras de llenar su palabra, y si la segunda carta es una $b$, entonces: ahora tengo dos consecutivas $b$'s, así que si $M=3$, luego el tercero, de la carta debe ser $a$, lo que nos deja con $F_{N-3}$ maneras de llenar la palabra. De nuevo, usted tiene la fórmula $F_N = F_{N-1} + \cdots F_{N-M}$.

Y así sucesivamente.

Answer 2

Aquí es una fórmula que se puede aplicar para averiguar el número de palabras,

Vamos N el número total de caracteres, ejecute i (número de b) = 1 a N y p (no de pares, por ejemplo , cada b tendrá que ser contado como 0 par y bb se cuenta como 1 par , bbb dos pares, y así sucesivamente y su estado de estados que no pueden tener igual o mayor que M-1 par donde M es el total consecutivas b), ejecute p = 0 para M-2

A continuación, el número total de palabras sería

$$ = 1+ \sum_{i=1}^{i=N}\sum_{p=0}^{p = M-2} {(i-1)\choose p}{(N-i+1)\choose(i-p)}$$ and disregard places where you have ${l\elegir k} $when $l<k$.