The number of words of length $n$ from specific alphabet with rule of creating.

Question

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 ?

Answer 1

From @shardulc 's analysis it follows that $$k_n=p_n+q_n=(p_{n-1}+q_{n-1}+q_{n-1})+2k_{n-1}=3 k_{n-1}+2k_{n-2}\ ,$$ or $$k_n-3k_{n-1}-2k_{n-2}=0\qquad(n\geq2)\ ,\tag{1}$$ with the initial conditions $k_0={1\over2}q_1=1$, $k_1=4$. We now proceed according to the rules of the Master Theorem. The characteristic equation $\lambda^2-3\lambda-2=0$ of $(1)$ has the roots $\lambda_\pm={1\over2}(3\pm\sqrt{17})$. It follows that there are constants $c_+$ and $c_-$ with $$k_n=c_+{\lambda_+}^n +c_-{\lambda_-}^n\qquad(n\geq0)\ .$$ The initial conditions then determine the two constants, and one obtains definitively $$k_n={1+5/\sqrt{17}\over2}\left({3+\sqrt{17}\over2}\right)^n +{1-5/\sqrt{17}\over2}\left({3-\sqrt{17}\over2}\right)^n\qquad(n\geq0)\ .\tag{2}$$ Here the second term is already for $n=0$ negligible, so that we can replace $(2)$ by $$k_n={\rm round}\left({1+5/\sqrt{17}\over2}\left({3+\sqrt{17}\over2}\right)^n \right)\ .$$ The numbers produced in this way are $$1,\quad4,\quad 14,\quad 50,\quad 178,\quad 634,\quad 2258,\quad 8042,\quad 28642, \quad102010,\quad 363314,\ \ldots\ .$$

Answer 2

If $a$ and $b$ are not adjacent in a sequence, we call it a valid sequence. Let the number of valid sequences of length $n$ ending with $a$ or $b$ be $p_n$, and let the number of valid sequences of length $n$ ending with $c$ or $d$ be $q_n$. Let the total number of valid sequences of length $n$ be $k_n$.

The first equation is $$k_n = p_n + q_n$$ We also know $$p_n = p_{n-1} + 2q_{n-1}$$ because a sequence ending with $a$ or $b$ can be formed by appending a $b$ or a $a$ to a sequence in $p_{n-1}$ ending with $a$ or $b$ (respectively), or by appending $a$ or $b$ to any sequence in $q_{n-1}$. Also, $$q_n = 2k_{n-1}$$ as we can append $c$ or $d$ to any valid sequence of length $n-1$.

Using these three, we can write $$ \begin{align} k_n &= p_n + q_n \\ &= p_{n-1} + 2q_{n-1} + 2k_{n-1} \\ &= p_{n-2} + 2q_{n-2} + 4k_{n-2} + 2k_{n-1} \\ &= \ldots \\ &= p_1 + 2q_1 + 4k_1 + 4k_2 + \dotsb + 4k_{n-2} + 2k_{n-1} \\ &= p_1 + 2q_1 + 4(k_1 + k_2 + \dotsb + k_{n-2}) + 2k_{n-1} \end{align} $$

We see that $p_1 = 2$ and $q_1 = 2$, and $k_1 = 4$. Thus $$k_n = 4(k_1 + k_2 + \dotsb + k_{n-2}) + 2k_{n-1} + 6$$

Though we cannot solve this recurrence directly, the first few values of $k_n$ are $4, 14, 50, 178, 634$ for $n = 1, 2, 3, 4, 5$. According to OEIS, there is only the closed-form $$k_n = \frac{5+\sqrt{17}}{2\sqrt{17}} \cdot \bigg(\frac{3+\sqrt{17}}{2}\bigg)^n - \frac{5-\sqrt{17}}{2\sqrt{17}} \cdot \bigg(\frac{3-\sqrt{17}}{2}\bigg)^n$$ as obtained by @ChistianBlatter.

Answer 3

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*}