Exponential generating function problem

Question

How many words are there of length $n$ that can be written with letters $A,B,C$ (letter indices) such that two letters $A$ are not neighbors?

How to evaluate exponential generating function for this problem? Also, how to include not neighbors condition in that function?

Answer 1

This problem seems more suitable for an OGF than an EGF. Using $z$ for any letter $A,B$ or $C$ and $w$ for $B$ or $C$ we obtain

$$(1+zw+z^2w^2+\cdots) \left(\sum_{q\ge 0} z^q (zw+z^2w^2+\cdots)^q\right) (1+z).$$

This is

$$\frac{1}{1-zw} \frac{1}{1-z\times zw/(1-zw)} (1+z) \\ = \frac{1+z}{1-zw-z^2w}.$$

Now for $w$ we have two choices and we finally obtain the OGF

$$\frac{1+z}{1-2z-2z^2}.$$

As a quick check the DFA method produces

> GFNC([[0,0]], 3, true);
                                   [[0, 0]]

                                 Q[], 0, Q[0]

                                 Q[], 1, Q[]

                                 Q[], 2, Q[]

                               Q[0], 0, Q[0, 0]

                                 Q[0], 1, Q[]

                                 Q[0], 2, Q[]

                             Q[0, 0], 0, Q[0, 0]

                             Q[0, 0], 1, Q[0, 0]

                             Q[0, 0], 2, Q[0, 0]

                                     z + 1
                               - --------------
                                    2
                                 2 z  + 2 z - 1