Number of Sequences of $1$'s $2$'s and $3$'s with Restriction

Question

We want to write down a sequence of $n$ numbers, where each number must be a $1,2$ or a $3$. The restriction is that there must be a $1$ between each two $2$'s and a $2$ between each two $1$'s. In how many ways can this be done?

Starting with $n=1$ we have simply $1,2$ or $3$ so these are only 3 ways.

for $n=2$ we can write $12,13,21,23,31,32,33$ so we have 7 ways.

For $n=3$ we have $$121,123,133,212,213,233,312,321,333,323,313,332,331,132,231$$

which is counted to be $15$. So we have the number of ways as the sequence $3,7,15,...$ for $n=1,2,3,...$.

Proceeding like this is not a smart way since we start getting lots of different permutations of these sequence. Is there any smart way of thinking?

Answer 1

If we construct the sequence term by term, we notice that after we encounter a $1$ or a $2$, we only have two options for each subsequent term, as we'll need a $2$ or a $1$ before we can write a $1$ or a $2$ again, respectively.

Thus, we can case on how many $3$'s are in the beginning of the sequence. Doing so, we get the sum $$\sum_{i=0}^n 2^{n-i} = 2^{n+1} - 1$$ where $i$ is the number of $3$'s starting the sequence (so $n-i$ is the amount leftover).

Answer 2

Suppose the list is not all $3$s. Choose which subset of the entries are $3$ in $2^n-1$ ways. What remains consists of a nonzero number $1$s and $2$s, and must alternate either $1212\dots$ or $2121\dots$ There are two choices, for a grand total of $(2^n-1)\cdot 2$ sequences. Adding in the sequence of all threes, you get $$2(2^n-1)+1=2^{n+1}-1.$$