Number of Words with two letters $a$ and $b$. Given $N$ and $M$, find the number of $N$ letter words consisting of only $a$ or $b$, where $b$ must not be consecutive for more than or equal to $M$ times.
Example: if $N=3$ and $M=2$, then all the possible words are: $\{aaa , aab , aba , baa , bab\}$.
 A: Here's an idea.
Fix $M$, and let $F_N$ denote the number of words such as you described of length $N$.
For a word of length $N$, it can either start with an $a$ or a $b$. If it begins with an $a$, you can fill the rest of the word in $F_{N-1}$ ways. If it begins with a $b$... Well, if $M=2$, then the second letter has to be an $a$, and this leaves you with $F_{N-2}$ ways of filling out the rest of the word. Thus $F_N = F_{N-1} + F_{N-2}$, which I could also write as $F_N = F_{N-1} + \cdots F_{N-M}$.
So suppose $M>2$, and that your word begins with a $b$. Then the second letter can be $a$ or $b$, and if it's an $a$, you are left with $F_{N-2}$ ways of filling out your word, and if the second letter is a $b$, then: I have now two consecutive $b$'s, so if $M=3$, then the third letter must be $a$, leaving us with $F_{N-3}$ ways to fill out the word. Again, you have the formula $F_N = F_{N-1} + \cdots F_{N-M}$.
And so on.
A: Here is a formula that you can apply to find out the number of words,
Let N be the total number of characters, run i (number of b's) = 1 to N and p (no of pairs, for example , each b will have to be counted as 0 pair and bb is counted as 1 pair , bbb is two pair, and so on and your condition states that you cannot have equal to or more than M-1 pair where M is the total consecutive b's), run p = 0 to M-2
Then the total number of words would be
$$ = 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\choose k} $when $l<k$.
