Coloring points in a cycle

Question

I have a question that relates to the Widom-Rowlinson model of statistical physics. Take a cycle on $n$ vertices. How many ways are there to color the $n$ vertices with the colors $\{\text{Red, Yellow, Blue}\}$ with the only restriction being that Red vertices cannot be next to Blue vertices? I'd like an explicit formula, if possible.

Answer 1

Consider the matrix $A = \pmatrix{1 & 1 & 0\cr 1 & 1 & 1\cr 0 & 1 & 1\cr}$. The number of ways to colour $\{0,1,\ldots, n\}$ subject to your restriction with $0$ coloured $i$ and $n$ coloured $j$ is $(A^n)_{ij}$ So the number of ways to colour your cycle is $\text{Tr}(A^n)$. Now $A$ has eigenvalues $1$, $1+\sqrt{2}$ and $1-\sqrt{2}$, so the answer is $1 + (1+\sqrt{2})^n + (1-\sqrt{2})^n$.