Take the 2-minute tour ×
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.

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|improve this question

1 Answer 1

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|improve this answer
2  
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

 
discard

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.