The string $AAABBAAABB$ is a string of ten letters, each of which is $A$ or $B$, that does include the consecutive letters $ABBA$. Determine, with justification, the total number of strings of ten letters, each of which is $A$ or $B$, that do not include the consecutive letters $ABBA$.
The conventional way of using casework is too simply and gives the right answer indeed but I am interested in getting the generating function.
The generating function is
$$F(x) = \left(1 – 2x + \frac{x^4}{1 + x^3}\right)^{-1}$$
which the coefficient of $x^{10}$ does give the right answer, but I am not sure how to get there.
How do I start?
Best Answer
This answer is based upon the Goulden-Jackson Cluster Method which is a convenient method to derive a generating function for problems of this kind.
We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[ABBA])&=-x^4-\text{weight}(\mathcal{C}[ABBA])x^3 \end{align*} and get \begin{align*} \text{weight}(\mathcal{C}[ABBA])=-\frac{x^4}{1+x^3} \end{align*}
$$ $$
The main theme is to properly cope with overlaps of bad words. In order to do so we introduce some terminology. Let $w=w_1w_2\ldots w_n$ be a word consisting of $n$ characters. We define \begin{align*} weight(w)&:=x^{length(w)}=x^n\\ HEAD(w)&:=\{w_1,w_1w_2,\ldots,w_1w_2\ldots w_{n-1}\}\\ TAIL(w)&:=\{w_n,w_{n-1}w_n,\ldots,w_nw_{n-1}\ldots w_2\}\\ OVERLAP(u,v)&:=HEAD(u)\cap TAIL(v) \end{align*}
If $x\in HEAD(v)$ we write \begin{align*} v&=xx^\prime\\ v/x&:=x^\prime \end{align*} and we define for convenience $u:v$ as sum over all overlaps of two words $u$ and $v$. We sum up the weighted left-over parts $v/x$ when chopping overlaps. \begin{align*} u:v:=\sum_{x\in OVERLAP(u,v)}weight(v/x) \end{align*}
Finally we find at the beginning of page 9 of the paper an identity for $weight(\mathcal{C}[v])$ with $Comp(v)$ defined as the set of bad words $u\in \mathcal{B}$ for which $OVERLAP(u,v)$ is non-empty. \begin{align*} weight(\mathcal{C}[v])=-weight(v)-\sum_{u\in Comp(v)}(u:v)\cdot weight\left(\mathcal{C}[u]\right) \end{align*}
Note: Although the notation looks somewhat complicated. With some routine you can skip nearly all of the calculations. We can deduce (3) quickly by observing that there is just one bad word $ABBA$ resulting in a term $x^4$ and one overlap \begin{align*} A&BBA\\ ABBA&\\ \end{align*} resulting in a term $x^{length(BBA)}=x^3$.