Recursion relation: Number of series length n made of (0,1,2)

Question

Recursion relation: Number of series length $n$ made of {$0,1,2$} so that in each series there are no two consecutive numbers that are the same, and there isn't $0$ in the middle (for an odd number of numbers).

So I divided it in this way:

1. $a_n$ is the series for strings in length of $2n+2$.
2. $b_n$ is the series for strings in lenght of $2n+1$.
3. $c_n$ is the series for strings in lenght of $n$.

So, for $a_n$ if I set $0$ as a first number, I can set $1$ or $2$ as a second number and then run for all the $a_{n-2}$ options. I do the same process with $1$ and $2$ and in total I will get $a_n=6a_{n-2}$.

For $b_n$, I can see what is the number of possibilities in $a_{n-1}$, and examine the possibilities in the middle:

1. If it has $01$,$02$,$10$,$20$ I have exactly 1 option to put a number in between them(so it won't be $0$ and won't be the same as it's neighbors).
2. If it has $12$ or $21$ I can't count this possibility.

So I can deduct than $b_n=\frac{2}{3}a_{n-1}$

So in total, for $2n+2$ numbers I have $6a_{n-2}+\frac{2}{3}a_{n-1}$.

First of all I wanted to ask if I'm at the right direction? Second, I don't sure how return back to $c_n$. Can I just define $c_n=a_{\frac{n}{2}-1}$ and just replace the indexes? Is there a way to simplify the equation?

Answer 1

Ignoring the zero clause, this is equivalent to the chromatic polynomial of path graph of length n using 3 colors.

There are three options for the first number, and then two for each subsequent number, since they can’t share the number of their most recent predecessor.

So, if n is even, there are $3 \cdot 2^{(n-1)}$ different strings.

If n is odd, there are two possibilities for the middle digit. Again, each neighbor will have two possibilities, meaning that there are $2^n$ different strings.

Hopefully that makes sense. I’d advise looking at chromatic polynomials for a more clear understanding, but I’m also happy to try and provide more explanation myself.

Answer 2

Strings of even length behave very differently then strings of odd length. Let $e_n$ be the number of strings of length $2n$, and $d_n$ be the number of strings of length $2n+1$. Handle $d_n$ and $e_n$ separately.

For $d_n$, consider what the first and last symbol are. There are $2$ choices for the first, two for the last, and then the middle symbols can be chosen in $d_{n-1}$ ways. Therefore, $$ d_{n}=2\cdot 2\cdot d_{n-1},\tag{$n\ge 1$} $$ with the base case $d_0=2$. Can you get a similar recursion for $e_n$?