Number of words using $\{a,b,c,d,e\}$ without "de" and "abd" consider the words over the alphabet $\{a,b,c,d,e\}$ of length $7$. What is the number of words that does not contain "de" and "abd" ? 
A reasonable solution (I think) is to set $t_n$ to be the number of $n$-th long words without "de" and "abd",    and then to find a recurrence relation. From this recurrence we can compute $t_7$. 
What is that recurrence relation? Is there another solution without recurrence? 
Thanks! 
 A: The following answer is based upon the Goulden-Jackson Cluster Method. We consider the set of words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{a,b,c,d,e\}$$ and the set $B=\{abd,de\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $f(s)$ with the coefficient of $s^n$ being  the number of wanted words of length $n$.
According to the paper (p.7) the generating function $f(s)$  is
\begin{align*}
f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1}
\end{align*}
with $d=|\mathcal{V}|=5$, the size of the alphabet and $\mathcal{C}$ is the weight-numerator of bad words with
\begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[abd])+\text{weight}(\mathcal{C}[de])\tag{2}
\end{align*}

We calculate according to the paper
  \begin{align*}
\text{weight}(\mathcal{C}[abd])&=-s^3\\
\text{weight}(\mathcal{C}[de])&=-s^2-s\cdot\text{weight}(\mathcal{C}[abd])\tag{3}\\
\end{align*}
  so  that
  \begin{align*}
\text{weight}(\mathcal{C})=-s^3+\left(-s^2-s\cdot\left(-s^3\right)\right)=-s^2-s^3+s^4
\end{align*}
  The additional term on the right-hand side of (3) takes account of the overlapping of $ab\color{blue}{d}$ with $\color{blue}{d}e$.
We obtain according to (1) and (3)
  \begin{align*}
f(s)&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\
&=\frac{1}{1-5s+s^2+s^3-s^4}\\
&=1 + 5 s + 24 s^2 + 114 s^3 + 542 s^4 + 2577 s^5\\
&\qquad + 12\,253 s^6 + \color{blue}{58\,260} s^7 + 277\,012 s^8 + 1\,317\,124 s^9 +\cdots
\end{align*}
  where the last line was calculated with the help of Wolfram Alpha. 

Result: The blue marked coefficient of $s^{7}$  shows there are $\color{blue}{58\,260}$ words of length $7$ over the alphabet $\mathcal{V}$ which do not contain $abd$ or $de$.
A: Note: This answer is incorrect; see comments below for discussion

We can justify a recurrence as follows: as soon as there is a starting string that "fails to be" either de or abd, we can freely append any string that has no de nor abd.
We can fail produce a forbidden string in the following ways:


*

*Begin with b,c, or e. (3 ways, 1 slot used),

*Begin with d, followed by any letter besides e (4 ways, 2 slots used),

*Begin with a, followed by any letter besides b (4 ways, 2 slots used),

*Begin with ab, followed by any letter besides d (4 ways, 3 slots used).


This leads to the following recurrence:
$$
t_n = 3t_{n-1} + 8t_{n-2} + 4t_{n-3}; n \geq 3.
$$ 
The initial conditions are
$$
t_0 = 1, \quad t_1 = 5, \quad t_2 = 24.
$$
A: Here we use PIE the inclusion-exclusion principle to count the number of valid $7$-letter words from the alphabet $\{a,b,c,d,e\}$ which do not contain the bad words $\{abd,de\}$.

In order to do the job some kind of bookkeeping is helpful. We consider
  \begin{align*}
.\ .\ .\ .\ .\ .\ . &-\left(abd\ .\ .\ .\ .|de\ .\ .\ .\ .\ .\right)\tag{1}\\
&+\left(abd\ abd\ .|abd\ de\ .\ .|abde\ .\ .\ .|de\ de\ .\ .\ .\right)\tag{2}\\
&-\left(abde\ abd|abde\ de\ .|abd\, de\, de|de\ de\ de\ .\right)\tag{3}
\end{align*}

Comment:


*

*In (1) we count all $7$-letter words indicated by seven dots which gives $5^7$. Then we subtract all words which contain at least one bad word.
Since $abd$ consumes three characters and four are left for free assignment, we count $\binom{5}{1}5^4$ words of this kind and similarly $\binom{6}{1}5^5$ in the other case with the bad word $de$.

*In (2) we add words containing two bad words as compensation for those which we've subtracted twice in (1), noting that we also have to consider overlaps $abd$ with $de$ giving $\color{blue}{abde}$.

*In (3) we finally subtract words containing three bad words which were added twice in (2). For instance $abde\ abd$ occurs in $\color{blue}{abd\ abd\ .}$ as well as in $\color{blue}{abde\ .\ .\ .}$

*No more cases are left to consider, since words containing four or more bad words have length $>7$.

We obtain according to (1) to (3):
  \begin{align*}
5^7&-\left(\binom{5}{1}5^4+\binom{6}{1}5^5\right)\\
&\quad+\left(\binom{3}{2}5^1+2\binom{4}{2}5^2+\binom{4}{1}5^3+\binom{5}{2}5^3\right)\\
&\quad-\left(2\binom{2}{2}5^0+2\binom{3}{2}5^1+\binom{3}{2}5^0+\binom{4}{3}5^1\right)\\
&=78\,125-(3\,125+18\,750)+(15+300+500+1\,250)-(2+30+3+20)\\
&=78\,125-21\,875+2\,065-55\\
&\,\,\color{blue}{=58\,260}
\end{align*}

Note: The Goulden-Jackson Cluster method used in another post is based upon the PIE approach and conveniently hides all this bookkeeping from us.
