Find the number of $\{a,b,c,d\}$-strings of length $n$

88 Views Asked by At

I am asked to find the the number of $\{a,b,c,d\}$-strings of length $n\in\mathbb{N}$ such that each string contains an odd number of $a$'s, an even number of $b$'s and at least one $c$. I used exponential generating functions to solve this problem and I got the answer as $\frac{4^n-3^n+(-1)^n}{4}$:\begin{equation*} A: x+\frac{x^3}{3!}+\frac{x^5}{5!}+\dots=\frac{e^x-e^{-x}}{2} \end{equation*} \begin{equation*} B: 1+\frac{x^2}{2!}+\frac{x^4}{4!}+\dots=\frac{e^x+e^{-x}}{2} \end{equation*} \begin{equation*} C:x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots=e^x-1 \end{equation*} \begin{equation*} D:1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots=e^x \end{equation*} Multiplying them together, we obtain \begin{equation*} \frac{e^{2x}-e^{-2x}}{4}\cdot(e^{2x}-e^x)=\frac{e^{4x}-1-e^{3x}+e^{-x}}{4} \end{equation*} Thus \begin{align*} e^{4x}-1=\sum_{n=1}^{\infty}\frac{4^nx^n}{n!}=4x+\frac{4^2x^2}{2!}+\frac{4^3x^3}{3!}+\dots\\ -e^{3x}=-\sum_{n=0}^{\infty}\frac{3^nx^n}{n!}=-1-3x-\frac{3^2x^2}{2!}-\dots\\ e^{-x}=\sum_{n=0}^{\infty}\frac{(-1)^nx^n}{n!}=1-x+\frac{x^2}{2!}-\dots \end{align*} \begin{equation*} \Downarrow \end{equation*} \begin{equation*} e^{4x}-1-e^{3x}+e^{-x}=\frac{(4^2-3^2+1)x^2}{2!}+\frac{(4^3-3^3-1)x^3}{3!}+\dots \end{equation*} Hence, for $n\geq2$, the coefficient of $\frac{x^n}{n!}$ is \begin{equation*} \frac{4^n-3^n+(-1)^n}{4} \end{equation*} However, as I check this formula there is a problem: If $n=3$, since the number of $a$ is odd, $b$ is even and there must be at least one $c$, the only possibility is to make strings of one $a$, one $c$ and one $d$ and thus there are only $6$ desired strings, which is unequal to $\frac{4^3-3^3+(-1)^3}{4}=9$. I wonder how to deal with this.