Recurrence Relation - coloring $n$ sectors on a circular disk

Question

A circular disk is divided into $n$ sectors labeled $1,2,3,\dots, n$. One wants to paint each sector in such a way that no two adjacent sectors receive the same color. Assume there are $6$ colors.

(a) Find a recurrence relation for $a_n$.

So far I have:

$n=2$: There are $6$ color choices for sector 1, and $5$ choices for sector 2. So there are $6\cdot 5 = 30$ ways to paint the sectors. So $a_2=30$.

$n=3$: There are $6$ color choices for $S_1$ and $5$ color choices for $S_2$ (cannot be color chosen for $S_1$). There are $4$ color choices for $S_3$ (cannot be color chosen for $S_1$ and $S_2$. So there are $6\cdot 5 \cdot 4 = 120$ ways to color the disk. So $a_3=120$.

$n=4$: There are $6$ color choices for $S_1$ and $5$ color choices for $S_2$. There are $5$ choices for $S_3$ (cannot be color chosen for $S_1$ but can be color choice for $S_2$. There are $5$ color choices for $S_4$ (cannot be color chosen for $S_2$ and $S_3$ but can be color for $S_1$.

$\textbf{Not sure if this is right...does this have to be split into cases?}$.

I found $a_4=750 = 6\cdot 5\cdot 5 \cdot 5$ by doing it this way.

Any help is appreciated...not sure if I am going about this problem the right way.

Answer 1

This is assuming that by "sector," you mean "slices of pie," then all you're asking is how many $6$-colorings $C_n$ has where $C_n$ is the $n$-cycle. To count this, as you did, let $a_n$ be the number of proper $6$-colorings of $C_n$. Fix your favorite vertex $v$; we will case on what happens to the neighbors of $v$. Firstly, if the neighbors have the same color, then we could consider removing $v$ and identifying these two neighbors and end up with a proper $6$-coloring of $C_{n-2}$, so there are $5\cdot a_{n-2}$ ways for this to happen. On the other hand, if they have different colors, then we could just consider removing $v$ and making it's neighbors adjacent and wind up with a proper $6$-coloring of $C_{n-1}$, so there are $4\cdot a_{n-1}$ for this to happen. Thus, $a_n=4a_{n-1}+5a_{n-2}$ with the base cases which you've already determined.

Answer 2

Let $a_n$ be the number of ways of the coloring of n sectors with $k$ colors. for the first sector, there are $k$ ways and for the second sector there are $k-1$ ways, similarly the $n^{\text{th}}$ sector could be colored in $k-1$ ways, but this will include the case when it is same as the $1^{\text{st}}$ sector or different from it;

$\therefore $ $a_n$ + $a_{n-1}$ = $k(k-1)^{n-1}$