<s>[INST] The number of words of length $n$ from specific alphabet with rule of creating. Determination of the number of words of length n formed from the alphabet $\{ a, b , c, d \} $, where the letters $a , b $ are not adjacent.
How to find out a recurrence and explicit formula for it ?
 [/INST] For problems like this the Goulden-Jackson Cluster Method is a convenient method to derive a generating function. The coefficients of this function are the wanted numbers.

We consider the set of words in $ \mathcal{V}^{\star}$ of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{a,b,c,d\}$$ and the set $B=\{ab,ba\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a 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}|=4$, the size of the alphabet and with the weight-numerator $\mathcal{C}$ with
  \begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[ab])+\text{weight}(\mathcal{C}[ba])
\end{align*}
  We calculate according to the paper
  \begin{align*}
\text{weight}(\mathcal{C}[ab])&=-s^2-\text{weight}(\mathcal{C}[ba])s\\
\text{weight}(\mathcal{C}[ba])&=-s^2-\text{weight}(\mathcal{C}[ab])s\\
\end{align*}
  and get
  \begin{align*}
\text{weight}(\mathcal{C}[ab])=\text{weight}(\mathcal{C}[ba])=-\frac{s^2}{1+s}
\end{align*}
It follows
  \begin{align*}
f(s)&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\
&=\frac{1}{1-4s+\frac{2s^2}{1+s}}\\
&=\frac{1+s}{1-2s-3s^2}
\end{align*}

Partial fraction decomposition and expansion of $f(s)$ results in

\begin{align*}
f(s)&=
\frac{1}{2}\left(1+\frac{5}{\sqrt{17}}\right)\cdot\frac{1}{1-\frac{3+\sqrt{17}}{2}s}+\frac{1}{2}\left(1-\frac{5}{\sqrt{17}}\right)\cdot\frac{1}{1-\frac{3-\sqrt{17}}{2}s}\\
&=\frac{1}{2}\left(1+\frac{5}{\sqrt{17}}\right)\sum_{n=0}^\infty\left(\frac{3+\sqrt{17}}{2}\right)^ns^n
+\frac{1}{2}\left(1-\frac{5}{\sqrt{17}}\right)\sum_{n=0}^\infty\left(\frac{3-\sqrt{17}}{2}\right)^ns^n\\
&=1+4s+14s^2+50s^3+178s^4+634s^5+\mathcal{O}(s^6)
\end{align*}

</s>