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.

  • $\begingroup$ I know how to solve it in this way, but I was asked to use recursion. $\endgroup$
    – Igor
    Jan 5 '19 at 11:29
  • $\begingroup$ Mike Earnest's post phrases it recursively. $\endgroup$ 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$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.