0

I have been given the following problem:
Find a recurrence relation for the number of ternary strings $(0,1,2)$ of length $n$ such that
(a) they do not contain $22$ as a substring
(b) they do not contain, neither $20$ nor $22$, as a substring

I have done the same steps from Recurrence Relations with ternary strings, and for (a) I get the recurrence relation $a_n=3a_{n-1}-a_{n-2}$, with $a_1=3$ & $a_2=8$.
I wrote down $a_1$ and $a_2$ manually:
$a_1=0,1,2$
$a_2=00,01,02,10,11,12,20,21$

Am I correct in working out that for (b), the recurrence relation is $a_n=3a_{n-1}-2a_{a-2}$, with $a_1=3$ and $a_2=7$?
I mean, there are 2 options being excluded instead of a single option...
Again, I wrote down $a_1$ and $a_2$ manually:
$a_1=0,1,2$
$a_2=00,01,02,10,11,12,21$

Martin Sieburg
  • 143

1 Answers1

0

For $n=3$ we have the good strings $$\{210,211,212,000,001,002,010,011,012,021,100,101,102,110,111,112,121\}$$

So $a_3=17$, not $3\times 7-2\times 3=15$ as you claim.

I would argue: For $n>2$, a good string of length $n$ can begin with $0$ or $1$ and then end with any good word of length $n-1$. Or it can begin with $21$ followed by any good word of length $n-2$. Thus $$a_n=2a_{n-1}+a_{n-2}$$

Note that this gives $a_3=17$ as desired.

Similarly, for the first part, I see $A_3=22$ as we have the good strings $$\{000,001,002,010,011,012,020,021,100,101,102,110,111,112,120,121,200,201,202,210,211,212\}$$

Whereas your formula gives $21$. The reasoning as above yields $A_n=2(A_{n-1}+A_{n-2})$.

(side note: I strongly recommend not using the same variables to denote different things. Here, you used $a_n$ in both parts. I switched the first part to $A_n$ to avoid the confusion).

lulu
  • 70,402