Exponential generating function to count strings

Question

I am struggling with the following exercise: "Determine a closed form formula for an egf that counts total strings of length $n$ with the restricted alphabet $\{A,B,C,D,E,F,F,G\}$ (not all letters must be used) such that an even number of $C$ letters are used, and at least one $G$ is used. If $a_n$ is the number of total strings, find a closed form for $a_n$.

I think I know how to get the form for $a_n$ once I have the egf but I am having some trouble finding the egf itself. I guess it makes it hard that there are two constraints. I would appreciate some help with this problem

Answer 1

For the letters with no contraints (all except $C$ and $G$), the EGF is $e^x=\sum_{k\ge 0}1\cdot \frac{x^k}{k!}$. This is because for any choice of locations, there is $1$ way to fill them with that letter.

For $G$, the EGF is instead $$ 0\cdot x^0+1\cdot x+1\cdot\frac{x^2}2+\dots=e^x-1 $$ This is just like the previous EGF, except the coefficient of $x^0/0!$ is now $0$ instead of $1$. This is because it is no longer legal to have zero $G$'s.

The trickiest is $C$. When $k$ is even, the coefficient of $x^k/k!$ should be $1$, and when $k$ is odd, the coefficient should be zero. The EGF looks like $$ 1+\frac{x^2}2+\frac{x^4}{4!}+\dots $$ It turns out the closed form for this is $$ (e^x+e^{-x})/2 $$ This is a common trick; the idea is that when you add $e^x$ to $e^{-x}$, the odd powers of $x$ cancel out, while the even powers are doubled. Dividing by two then gives a series where the coefficient of $x^k/k!$ is one if $k$ is even and zero if $k$ is odd.

Finally, you must multiply all seven EGF's together. The result is $$ (e^x)^5\cdot (e^x-1)\cdot (e^x+e^{-x})/2. $$

Answer 2

There are four classes of string: with odd or even number of $C$, and with zero or non-zero number of $G$. The first step would be to set up mutual recurrences for the number of strings in each class.