Combinatorics: making a 4-letter word from {a, b} Question: Given the letters $\{a, b\}$, how many 4 letter 'words' can one make? Define the weight of a word of the number of instances of 'ab' in it. How many instances are there of weight 0, 1, and 2? Find a generating function. Do the same for 5, 6, and n-letter words.
My approach:
Since you have two choices for each letter, you have $2^n$ choices, where $n$ is the length of the word. So for the first case, the 4 letter word, we have $2^4 = 16$ choices for words. I found the number of words with weights 0, 1, and 2 by brute force and got 5, 10, and 1, respectively. I'm not sure how to do that more easily, as in, not with brute force but with some sort of combinatorial logic.
Then, we get the series $5 + 10x + x^2$ but this isn't an infinite series so I have no idea how to find a generating series for it.
If anyone has any hints for how to solve this problem, please let me know, any help would be appreciated. Thanks!
 A: HINT & more
Here is a more elementary answer.  The key is the number of transitions in the $n$-letter word, where a transition is two adjacent letters which are different.  Since the alphabet has only two letters, transitions must alternate between $ba$ and $ab$, and of course the weight is the no. of $ab$ transitions.
If the word begins with $b$ and ends with $a$, then it has weight $w$ iff it has $2w+1$ transitions: the odd-numbered i.e. $1$st, $3$rd, $5$th, ..., $(2w+1)$-th transitions are $ba$ and the even-numbered transitions are $ab$.
Now an $n$-letter words can begin with either letter and end with either letter, but if we imagine there is an extra $b$ at the front and an extra $a$ at the end, then the new "augmented" $(n+2)$-letter word will have weight $w$ iff it has $2w+1$ transitions, and since the imaginary extra letters cannot be part of any $ab$, all these $w$ instances of $ab$ transitions are in the original $n$-letter word.  E.g. $(b)aabbaba(a)$ has $5$ transitions and therefore weight $w=2$ (for either the original $7$-letter word or the augmented $9$-letter word).
The above should be enough for you to finish, but just in case...

In the $(n+2)$-letter word, there are $n+1$ places for transitions, so there are ${n+1 \choose 2w+1}$ ways to place the $2w+1$ transitions.  Consequently, the number of $n$-letter words with weight $w$ is precisely ${n+1 \choose 2w+1}$ and the generating function is

$f_n(x) = \sum_{w=0}^{\lfloor n/2 \rfloor} {n+1 \choose 2w+1} x^w $

Note that for $n=5$ and $n=6$ this gives 


*

*$f_5(x) = 6 + 20 x + 6 x^2$ 

*$f_6(x) = 7 + 35 x + 21 x^2 + 1 x^3$
which are different from what you (manually?) counted.  E.g. if you consider the $n=5, w=2$ case, my $f_5(x)$ above has $6 x^2$ corresponding to the six words $ababa, ababb, abbab, abaab, babab, aabab$.
A: http://algo.inria.fr/flajolet/Publications/book.pdf is an amazing resource for this kind of stuff.
Using the language of Flajolet, we have that the class of all binary words is given by $\text{Seq}(\mathcal{A})$, where $\mathcal{A} = \{a,b\} \cong Z = Z$. This is given by the power series of $\frac{1}{1-(z+z)} = \frac{1}{1-2z}$. Now take the Taylor series to get that we have this corresponds to the series $\sum_0^\infty 2^nz^n$, and to find the number of words of length four, we find $[z^4]\left(\sum_0^\infty 2^n z^n \right) = 2^4$, as you predicted.
We want to now use the language to try to count the number of times that "ab" appears; i.e., we want to somehow flag "ab" so that we can pull the coefficient from the Taylor series out. How do we do this? This is similar to example I.10 in the book. Flajolet defines the space of all words in the following way:
$$ \mathcal{W} \cong \text{Seq}(b)\text{Seq}(a\text{Seq}(b)b\text{Seq}(b))\text{Seq}(a).$$
He does this in order to count double runs, but we can abuse this to get what we want by flagging the parts we care about, i.e., the middle part. We then get the generating function
$$ \frac{1}{1-z}\cdot\frac{1}{1-tz(1/(1-z))z(1/(1-z))}\cdot\frac{1}{1-z} = \frac{1}{1-(t-1)z^2-2z},$$
where the $t$ will keep track of how many $ab$'s we have. Checking the coefficient of $z^4$ in the Taylor series of the above, for example, gives us 
$$ t^2 + 10t + 5,$$
which is what you also got (the coefficient of $t^n$ corresponds to weight $n$). So for words of size $m$, we just need to get the $m$th coefficient of this Taylor series, and we will get the corresponding power series for the weights.
