Coloring dots in a circle with no two consecutive dots being the same color

Question

I ran into this question, it is not homework. :)

I have a simple circle with $n$ dots, $n\geqslant 3$. the dots are numbered from $1\ldots n$.

Each dot needs to be coloured red, blue or green. No dot can be couloured the same as his neighbors. How many options are there to organize the colours?

Hint: we need to use recurrence relation.

Answer 1

Let $a_n$ be the number of ways of coloring a ring of $n$ dots. Now consider a ring of $n+1$ dots that have been properly colored. There are two possibilities: either dots $1$ and $n$ have the same color, or they do not.

• If they do not have the same color, then removing dot $n+1$ leaves one of the $a_n$ properly colored rings of $n$ dots. Conversely, if we insert a dot $n+1$ into a properly colored ring of $n$ dots, we must give it the third color in order to have a properly colored ring of $n+1$ dots. Thus, there are $a_n$ properly colored rings of $n+1$ dots in which dots $1$ and $n$ have different colors.

• If dots $1$ and $n$ have the same color, imagine removing dot $n+1$ and merging dots $1$ and $n$ into a single dot; you now have a properly colored ring of $n-1$ dots. Conversely, if you start with a properly colored ring of $n-1$ dots, you can split dot $1$ into two dots of the same color, one adjacent to dot $2$ and one adjacent to dot $n-1$; call the former dot $1$ and the latter dot $n$. Now insert dot $n+1$ between the new dots $1$ and $n$; this time you have two choices for its color, so there are $2a_{n-1}$ properly colored rings of $n+1$ dots in which dots $1$ and $n$ have the same color.

The recurrence is therefore $a_{n+1}=a_n+2a_{n-1}$, and I’ll leave it to you to work out the initial conditions.

Answer 2

$$A_{n+2} = A_{n+1}+2*A_{n}$$

for a coloring of a sequence of dots $d_1,d_2,...,d_n$, it is a valid coloring iff one of two mutually exclusive conditions is met.

(1) $d_1\ne d_n\ne d_{n-1}\ne d_1$ and $d_1,d_2,...,d_{n-1}$ is a valid coloring.

(2) $d_1 = d_{n-1}\ne d_{n-2}$ and $d_n\ne d_1$ and $d_1,d_2,...,d_{n-2}$ is a valid coloring.

in the first case, each unique choice of $d_1,d_2,...,d_{n-1}$ yields a unique choice for $d_n$, and in the second case, each choice of $d_1,d_2,...,d_{n-2}$ yields a unique choice for $d_{n-1}$ and two possibilities for $d_n$. these possibilities do not overlap, so we simply add them.

Answer 3

Let $A_n$ be the number of ways you can colour your circle of $n$ dots, and let $B_n$ be the number of ways you can colour a line of $n$ dots. Of course $B_n$ is much easier to figure out: we have a choice of $3$ colours for the dot on the left end, $2$ colours for the one next to it, $2$ for the next, and so on, so $B_n=3\cdot 2^{n-1}$ for $n\ge 1$.

Next, observe that $B_n=A_n+A_{n-1}$ for $n\ge 3$. This is because (as explained in the other answers) the number of ways to colour the line of $n$ dots with different colours at the ends is equal to $A_n$, while the number of ways to do it with the same colour at both ends is equal to $A_{n-1}$.

This gives us the recurrence $A_n=B_n-A_{n-1}=3\cdot 2^{n-1}-A_{n-1}$ which is valid for $n\ge 3$. The initial value, of course, is $A_2=6$. The next few values are: $$A_3=B_3-A_2=12-6=6;$$ $$A_4=B_4-A_3=B_4-B_3+A_2=24-12+6=18;$$ $$A_5=B_5-A_4=B_5-B_4+B_3-A_2=48-24+12-6=30;$$ and so on.

The pattern is clear: $A_n$ is the sum of a geometric progression of $n-1$ terms with first term $a=B_n=3\cdot 2^{n-1}$ and common ratio $r=-\frac 1 2$. Plugging these values into the formula $\frac{a(1-r^n)}{1-r}$ and simplifying, we get $A_n=2^n+2(-1)^n$.