How many series of length $n$ combined from the numbers $0,1,3,4$ , that don't contain the sequences $04,40,13,31$ or $0X0, 1X1, 3X3, 4X4$ are there?

Question

How many series of length $n$ combined from the numbers ${0,1,3,4}$ , that don't contain the sequences $04,40,13,31$ or $0X0, 1X1, 3X3, 4X4$ (where X can be any number from $0,1,3,4$) are there? Let $f(n)$ be the number of the good series of length $n$.

If I start with $1$, then I have $f(n-1)$ options for the rest of the series without limitations, but I have to decrease the series of length $(n-2)$ starting with 3 (so I won't have $13$ in my series) and I have to decrease 3 times the series of length $(n-3)$ starting with 1 (so I won't have $1X1$ in my series). Overall $f(n)$ is 4 times the process I just did because of symmetry depending on the first number in the series, i.e. $f(n)=4(f(n-1)-f(n-2)-3f(n-3))$.

I know I have a mistake when I'm decreasing the series of length $(n-2)$ becuse I'm decreasing too much.

Would appreciate any help in correcting that mistake. Thanks:)

Answer 1

The restrictions can be put in a little simpler way by this small (not at all necessary) trick: modify the sequence at even times ($n=2,4,6\cdots)$ by remapping the values $0 \leftrightarrow 4$, $1 \leftrightarrow 3$... The prohibited subsequences then become $\cdots *XX*\cdots $ and $\cdots *X*X*\cdots$ . That is, we must have $x[n]\ne x[n-1]$ and $x[n]\ne x[x-2]$. Because the first restriction implies $x[n-1]\ne x[x-2]$, then the sequence construction follows a simple pattern: in each time we have $2$ alternatives, except for time $n=1$ when we have $4$, and time $n=2$ when we have $3$.

Hence, no need of recursions. The total number of sequences is $f(n) = 4 \times 3 \times 2 \times 2 \cdots 2$, or

$$ f(n)=\begin{cases} 4 & n=1\\ 4 \times3 \times2^{n-2}=3\times2^n & n>1 \end{cases} $$

Answer 2

As soon as I have a series of length $2$ or more it will end with a pair $\dots ab$

To add $c$ so we get $\dots abc$ we need to make sure that $c\neq a, 4-b$. This excludes two possibilities unless $a=4-b$, but in this case the sequence was already bad, so we can exclude it.

(This can also be used to analyse what happens at the start of the series).

There will be some special cases at the beginning where this analysis does not apply, but here can be done by hand.

I think you have overcomplicated your analysis - the exclusions depend on the actual elements of the series and you need to get under the skin of that before you start counting.