Recursive formula to the number of words length n with restrictions

Question

Looking for recursive formula to the number of words length $n$ with the letters $A,B,C $and the following restrictions: neither $AB$ nor $CA$ can occur as a string in the word.

I tried to build a legal word from the start and tried to look at the last letter of a word of length $n-1.$ The problem is, there is a difference between the number of options for letters to follow $A,C$ than the number of options for letters to follow $B$.

Answer 1

Let $a_n$ be the number of legal strings of length $n$ that end in $A$, $b_n$ the number that end in $B$, and $c_n$ the number that end in $C$. Let $d_n=a_n+b_n+c_n$; $d_n$ is the total number of legal strings of length $n$. Then

$$\begin{align*} &a_n=a_{n-1}+b_{n-1}\;,\\ &b_n=b_{n-1}+c_{n-1}\;,\text{ and}\\ &c_n=a_{n-1}+b_{n-1}+c_{n-1}\;. \end{align*}$$

Thus, $c_n=d_{n-1}$, so we can rewrite the system as

$$\begin{align*} &a_n=a_{n-1}+b_{n-1}=d_{n-1}-c_{n-1}=d_{n-1}-d_{n-2}\;,\\ &b_n=b_{n-1}+c_{n-1}=d_{n-1}-a_{n-1}=d_{n-1}-d_{n-2}+d_{n-3}\;,\text{ and}\\ &c_n=a_{n-1}+b_{n-1}+c_{n-1}=d_{n-1}\;, \end{align*}$$

so that

$$d_n=a_n+b_n+c_n=3d_{n-1}-2d_{n-2}+d_{n-3}\;.$$

This sequence is OEIS A$034943$; there does not appear to be a nice closed form, though since the characteristic polynomial is only a cubic, in principle one can solve it and write down a closed form in terms of the roots.

Answer 2

As you pointed out, the recursion is complicated by the fact that there are a different number of options for letters that can follow $A,C$ than there are for letters that can follow $B$. To deal with that, we will split things up. Let $u_n$ be the number of unacceptable words of length $n;$ $a_n,b_n,c_n,$ the number of acceptable words of length $n$ ending in $A,B,C$ (respectively). So, we must keep in mind that $$u_n+a_n+b_n+c_n=3^n.\tag{$\star$}$$ (Do you see why?) I am assuming, here, that you do not count the "letterless word" as a word. If this is not the case, let me know. It's a fairly easy fix.

Clearly, $u_1=0$ and $a_1=b_1=c_1=1.$

Now, suppose we know $u_{n-1},a_{n-1},b_{n-1},c_{n-1}$ for some $n\ge 2,$ and take any word of length $n-1$. We observe the following:

• If the word is unacceptable, then concatenation of any of the three letters to the end of it produces an unacceptable word of length $n$.
• If the word is acceptable and ends with an $A,$ then concatenation of $A$ or $B$ to the end of it produces an acceptable word of length $n$, while concatenation of $C$ to the end of it produces an unacceptable word of length $n$.
• If the word is acceptable and ends with a $B,$ then concatenation of any of the three letters to the end of it produces an acceptable word of length $n$.
• If the word is acceptable and ends with an $C,$ then concatenation of $B$ or $C$ to the end of it produces an acceptable word of length $n$, while concatenation of $A$ to the end of it produces an unacceptable word of length $n$.

Combining the above observations, we see that $$u_n=3u_{n-1}+a_{n-1}+c_{n-1}\\a_n=a_{n-1}+b_{n-1}\\b_n=b_{n-1}+c_{n-1}\\c_n=a_{n-1}+b_{n-1}+c_{n-1}$$

---

The above presents the recurrence relation completely, but it is far from straightforward. One thing that may help, here, is to rewrite it in terms of vectors and matrices: $$\begin{bmatrix}3u_{n-1}+1a_{n-1}+0b_{n-1}+1c_{n-1}\\0u_{n-1}+1a_{n-1}+1b_{n-1}+0c_{n-1}\\0u_{n-1}+0a_{n-1}+1b_{n-1}+1c_{n-1}\\0u_{n-1}+1a_{n-1}+1b_{n-1}+1c_{n-1}\end{bmatrix}=\begin{bmatrix}u_n\\a_n\\b_n\\c_n\end{bmatrix}\\\begin{bmatrix}3 & 1 & 0 & 1\\0 & 1 & 1 & 0\\0 & 0 & 1 & 1\\0 & 1 & 1 & 1\end{bmatrix}\begin{bmatrix}u_{n-1}\\a_{n-1}\\b_{n-1}\\c_{n-1}\end{bmatrix}=\begin{bmatrix}u_n\\a_n\\b_n\\c_n\end{bmatrix}\\M\vec v_{n-1}=\vec v_n$$ It can then be seen that $$\vec v_n=M^n\vec v_0=M^n[0\:1\:1\:1]^t.$$ for all $n\ge 1.$ At that point, we can further observe that $[0\:1\:1\:1]\vec v_n$ will give the number of acceptable words of length $n$ for any $n\ge 1,$ so $$[0\:1\:1\:1]M^n[0\:1\:1\:1]^t$$ is the number of acceptable words of length $n$ for any $n\ge 1.$ It is possible that this observation, together with $(\star)$, may allow for the discovery of a closed form, or at least a simpler recursion, but I don't know for sure.