Determine the number of $n$-digit quaternary $\{0,1,2,3\}$ sequences $a_n$ in which there is never a $3$ anywhere to the right of a $0$.

Question

Determine the number of $n$-digit quaternary $\{0, 1, 2, 3\}$ sequences, $a_n$ in which there is never a $3$ anywhere to the right of a $0$. 20213 is thus a forbidden string of length 5. What is the initial condition? Formulate the RR and solve on the computer. How many such strings of length 50 are there?

Answer 1

Finishing from the hint I gave earlier... break into cases based on whether a zero appeared or not.

In the case that no zero appeared, every one of the $n$ positions could be any of the digits $\{1,2,3\}$, giving $3^n$ possible sequences.

In the case that a zero does appear, pick the position of the first occurring zero. There are $n$ options for this. Next, for all digits left of the first zero, they may be any of the digits $\{1,2,3\}$. Then, for all digits right of the first zero, they may be any of the digits $\{0,1,2\}$. In either case it is $3$ options per position in each of the $n-1$ positions giving $3^{n-1}$ possible ways to fill in the remaining positions.

The total number is then:

$$3^n+50\times 3^{n-1}$$

---

Now... if you insist on using a recurrence relation even though it is clearly not necessary for this problem (and indeed, makes it harder rather than easier), I recommend using the same observation I made above and breaking into two separate sequences.

Let $f(n)$ be the number of valid quaternary sequences of length $n$ where no $0$ appears. Let $g(n)$ be the number of valid quaternary sequences of length $n$ where a $0$ does appear.

We have initial conditions $f(0)=1$ and $g(0)=0$. (Don't forget that the empty sequence is still a sequence. If that bothers you too much, then we have initial conditions $f(1)=3$ and $g(1)=1$)

We have $f(n)=3\cdot f(n-1)$ and $g(n)=f(n-1)+3\cdot g(n-1)$

Finally we have the sequence we are actually interested in, the number of valid sequences of length $n$ regardless of whether or not a zero appeared will be $a(n)=f(n)+g(n)$