How many words of length $4$ can be formed by the following language $S =\{ a, bb\}$? Of course, I can list all of the different words


*

*$aaaa$

*$aabb$

*$abba$

*$bbaa$

*$bbbb$


and then count them. But I would like to find the answer in a more mathematical way, perhaps through combinatorics. Any help?
 A: For any word length $n$, we can have anywhere between $0$ and $\lfloor \frac{n}{2} \rfloor$ occurrences of $bb$. If we have, say, $B$ of them, then the number of distinct ways to order $B$ $bb$'s and $n-2B$ $a's$ is
$${{B + (n - 2B)}\choose{B}} = {{n - B}\choose{B}}.$$
Summing over the possible numbers $B$ of occurrences of $bb$ gives
$$\sum_{B = 0}^{\lfloor n / 2 \rfloor} {{n - B}\choose{B}}.$$
This turns out be nothing more than the $n$th Fibonacci number $F_n$ (where we take $F_0 = F_1 = 1$). See, e.g., http://mathworld.wolfram.com/PascalsTriangle.html .
For $n = 4$ the sum is
$${{4}\choose{0}} + {{3}\choose{1}} + {{2}\choose{2}} = 1 + 3 + 1 = 5,$$
which agrees with your count. These terms respectively correspond with the sets $\{aaaa\}, \{aabb, abba, bbaa\}, \{bbbb\}$.
A: Another way to show this is to let
$\;\;\;c_n$ be the number of words of length n, 
$\;\;\;a_n$ be the number of words of length n ending with "a", and
$\;\;\;b_n$ be the number of words of length n ending with "bb".
Then $c_n=a_n+b_n$ where $a_n=c_{n-1}$ and $b_n=c_{n-2}$; 
so we have $c_n=c_{n-1}+c_{n-2}$ with $c_1=1$ and $c_2=2$.  Thus $(c_n)$ is the Fibonacci sequence.
