2

I have 5 characters ${a,b,c,1,2}$. $a_n$ is the number of strings I can create for $n$ length. I can't have the following sequences in a string: $a1$, $b2$ and any sequence of numbers $(12, 21)$.

For example legal string: $aaaa$, $abb1$, $1aaa$ For example illegal string: $aaa1$, $11cc$, $c121$

I need to find a Recurrence relation for $a_n$ and also seed values.

I thought about the following: if the string starts with 1, 2, $a$ or $b$, I have to decide for $n-2$ places which means $4*f(n-2)$. If it starts with any other character, then it's $f(n-1)$, all together $a_n = 4*f(n-2) + f(n-1)$. I'm not sure it is correct due.

Thanks

essay
  • 1,135
user2102697
  • 67

1 Answers1

0

Change notation a bit. Let $s_n$ denote the number of legal strings of length $n$. Then introduce $a_n,b_n,c_n,1_n$ and $2_n$ respectively to denote the number of legal strings of length $n$ ending with $a,b,c,1$ or $2$ respectively. With this we have $$ s_n=a_n+b_n+c_n+1_n+2_n $$ where $$ a_n=b_n=c_n=s_{n-1} $$ because you can add $a,b$ or $c$ at the end of any legal string whereas $$ \begin{align} 1_n&=b_{n-1}+c_{n-1}\\ 2_n&=a_{n-1}+c_{n-1} \end{align} $$ so all together this yields $$ s_n=3\cdot s_{n-1}+4\cdot s_{n-2} $$

EDIT

Note that this relation only holds for $n\geq 3$ since otherwise it refers to strings of length $0$ which have no restrictions as to the next character. One can check that $s_1=5$ and $s_2=19$. With these seeds we obtain $$ s_n=\frac{6\cdot 4^n-(-1)^n}{5} $$ which can be confirmed by this Wolfram Alpha Solution.

String
  • 18,395