Problema de la función generadora exponencial

Question

¿Cuántas palabras hay de longitud $n$ que se puede escribir con letras $A,B,C$ (índices de letras) tales que dos letras $A$ ¿no son vecinos?

¿Cómo evaluar la función generadora exponencial para este problema? Además, ¿cómo incluir no vecinos en esa función?

Answer 1

Este problema parece más adecuado para un FGO que para un FEAG. Utilizando $z$ para cualquier letra $A,B$ o $C$ y $w$ para $B$ o $C$ obtenemos

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

Esto es

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

Ahora para $w$ tenemos dos opciones y finalmente obtenemos el OGF

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

Como comprobación rápida, el DFA método produce

\> 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