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

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?

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.

• I know how to solve it in this way, but I was asked to use recursion.
– Igor
Jan 5 '19 at 11:29
• Mike Earnest's post phrases it recursively. Jan 6 '19 at 18:45

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$$?