Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

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$.

share|cite|improve this answer
This is a very helpful perspective --- thanks! Typo in the last line of $A$, I assume --- row should be $0, 1, 1$? – John Engbers Jun 6 '12 at 18:23
Thanks, fixed it. – Robert Israel Jun 6 '12 at 23:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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