How many vertex-colorings with 3 colors has the cycle $C_n$? How to build a recursive equation for the number of colorings over n?
I know that a cycle has either 2 or 3 colors. 2 when n is even and 3 obviously when it is odd. But what could be the recursive equation?
I believe that the sequence would be such:
$$C_0 = 0$$ $$C_1 = 1$$ $$C_2 = 2$$ $$C_3 = 3$$ $$C_4 = 2$$ $$C_5 = 3$$ $$ \dots $$
I have tried using mod over n but it didn't seem to work out. Basically, it is hard to include the base cases of $C_0$ and $C_1$ in the recursive equation to make it complete.
Following Hennings comment.
Let $f_n$ be the sequences of length $n$ with symbols $\{1,2,3\}$ starting in $1$, ending in $2$ or $3$ and not containing repeated terms.
By inspection $f(3)=2,f(4)=6$. We now find a recursion for $f_{n+2}$, we classisfy the sequences of length $n+2$ in two kinds.
First kind:
Those with second to last character equal to $2$ or $3$, there are $f_{n+1}$ sequences of this kind since a sequence with second to last character $2$ must end in $3$ and a sequence with second to last character $3$ must end in $2$.
In other words a sequence of this type is determined by the first $n+1$ terms and there are $f_{n+1}$ ways to choose these.
Second kind:
Those in which the second to last character is equal to $1$. In this case when we consider the $n$ first characters we find a sequence of length $n-2$ of the kind we are considering (since the third to last character must be different from the second to last character). There are $f_{n}$ such sequence. Once the first $n$ character have been fixed we have by hypothesis that the $n+1$'th character (the second to las character) is $1$. So we have $2$ options for the last character. It can be $2$ or $3$. Hence there are $2f_n$ sequences of this kind.
This analysis yields the recurrence $f_{n+2}=f_{n+1}+2f_{n}$
The number of ways to color the n-gon is therefore $3f_n$ since it is possible that the sequence does not start in $1$, it may start with $2$ or $3$.