0
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ Do you mean that neither the string AB nor the string CA can appear in the word? Or do you mean that the word cannot have both of those strings? Also, what are your thoughts and efforts on the problem, so far? $\endgroup$ – Cameron Buie Nov 27 '13 at 23:40
  • $\begingroup$ Cannot have those two strings in the word. $\endgroup$ – zivik Nov 27 '13 at 23:43
  • $\begingroup$ That does not answer my question. The phrasing is ambiguous. In the first interpretation I offer, the word $AB$ is not acceptable, because the acceptable words are those with neither the string $AB$ nor the string $CA.$ In the second interpretation, though, the word $AB$ is acceptable, because it does not have both of those strings. $\endgroup$ – Cameron Buie Nov 27 '13 at 23:45
  • $\begingroup$ You can't have any one of the 2 $\endgroup$ – zivik Nov 27 '13 at 23:47
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @Cameron: On the other hand, yours is a bit less ad hoc and therefore generalizes better. $\endgroup$ – Brian M. Scott Nov 28 '13 at 0:47
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.