formula for the number of words with length n Using exponential generating functions, find a formula for the number of words of length $n$ made from the letters $a$, $b$, $c$, and $d$ and which contain at least one $a$, at least one
$b$, and at least one $c$.
I am not sure how to approach this.
I understand that since it should contain at least one $a$, one $b$, and one $c$, $n$ cannot be $0,1,2$, so $n=3$ or $n=4$.
I am not sure how to generate a formula for this.
A start to this will be appreciated.
 A: The crucial fact about exponential generating functions is this: Given two labelled structures $\mathcal{A}$ and $\mathcal{B}$, with exponential generating functions $A(z)$ and $B(z)$, their labelled product $\mathcal{A} \star \mathcal{B}$ (which means, essentially, all ways of picking an element from $\mathcal{A}$, an element from $\mathcal{B}$, and interleaving them)  has exponential generating function $A(z) B(z)$.
A word over an alphabet is essentially all ways of interleaving the occurrences of each letter in the alphabet.
Let $\mathcal{A} = \{a, aa, aaa, aaaa, \dots\}$ so that it has EGF $A(z) = z + \frac{z^2}{2!} + \frac{z^3}{3!} + \dots = e^z -  1$.
Similarly let $\mathcal{B} = \{b, bb, bbb, bbbb, \dots\}$ with EGF $B(z) = A(z) = e^z - 1$, and $\mathcal{C} = \{c, cc, ccc, cccc, \dots\}$ with EGF $C(z) = A(z) = e^z - 1$, and finally $\mathcal{D} = \{\epsilon, d, dd, ddd, dddd, \dots\}$ (here $\epsilon$ denotes the empty string) with EGF $D(z) = e^z$.
Here we want the EGF for $\mathcal{A} \star \mathcal{B} \star \mathcal{C} \star \mathcal{D}$, which is therefore
$$\begin{align}
A(z)B(z)C(z)D(z) 
&= (e^z-1)(e^z-1)(e^z-1)e^z  \\
&= e^z(e^{3z} - 3e^{2z} + 3e^z - 1) \\
&= e^{4z} - 3e^{3z} + 3e^{2z} - e^z
\end{align}$$
giving the formula for the words of length $n$ as
$$n![z^n]\big(A(z)B(z)C(z)D(z)\big) = 4^n - 3(3^n) + 3(2^n) - 1$$
[Note that we get the same answer via combinatorial counting using the inclusion-exclusion principle: there are $4^n$ words in all without the "at least one a" and similar constraints, from which we must subtract $3^n$ each to leave out words with no a, no b, and no c, then add back $2^n$ for each of the $\binom{3}{2}$ pairs that we overcounted, and finally subtract the $1$ coming from the unique word of length $n$ that has only the letter d in it.]
