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.

Given a graph with $2n$ nodes named by $u_1,u_2\cdots u_n$ and $v_1,v_2\cdots v_n$.

The graph is given like this: $\forall 1\le i\le n$, there is an edge between $u_i$ and $v_i$, and there is also an edge between $u_i$ and $u_{i+1}$ as well as $v_i$ and $v_{i+1}$($u_{n+1}$ is considered as $u_1$, so as $v_{n+1}$). My question is, how many method are there to color the graph with three colors?

By doing some experiment, denote the number of method by $C(n)$, I know that it follows a recurrence equation(I know it by a experiment result of testing $n=3,4,\cdots 10$, not giving a precise proof) $C(n)=2C(n-1)+5C(n-2)-6C(n-3),C(3)=12,C(4)=114,C(5)=180$. I have tried induction, but without any idea of proving this recurrence equation, any hints or solutions are welcomed. Thanks for attention!

share|improve this question
    
Do you have a proof of the recurrence, or is it part of the question? –  Christian Blatter Jan 17 '13 at 11:33
    
@ChristianBlatter proving the recurrence is part of the question, sorry of my ambigous question.. –  Golbez Jan 17 '13 at 12:55

3 Answers 3

up vote 4 down vote accepted

Call the three colors $0$, $1$, $2$. Each rung $(u_i,v_i)$ of your "circular ladder" can then be colored in one of the six ways $01$, $12$, $20$, $10$, $21$, $02$. Assume $(u_0,v_0)$ is colored $01$. Each admissible coloring of the full ladder then corresponds to a closed path $\gamma$ of length $n$ beginning and ending at the node $01$ in the following auxiliary graph:

enter image description here

Count a counterclockwise movement along a leg of one of the triangles as $+1$ and a clockwise movement as $-1$. If $\gamma$ contains $m\leq n$ movements along a triangle leg, counting $x_i\in\{-1,1\}$ $\ (1\leq i\leq m)$, then we must have $$\sum_{i=1}^m x_i=0\quad({\rm mod}\ 3)\ .\qquad(*)$$ Given $m$ it is easy to verify by induction that the number of solutions of $(*)$ is $$b_m={1\over3}\bigl(2^m +2(-1)^m\bigr)\ .$$

The closed path $\gamma$ has to contain an even number of changes from the outer to the inner triangle or vice versa. Given $k$ with $0\leq k\leq\lfloor{n\over2}\rfloor$ the $2k$ jump times can be chosen in ${n\choose 2k}$ ways.

Dropping the assumption that the rung $(u_0,v_0)$ is colored $01$ we therefore get a total of $$C(n)=6 \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} b_{n-2k}=2 \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k}\bigl(2^{n-2k}+2(-1)^n\bigr)$$ such paths, resp., admissible colorings of our circular ladder.

Using the formula $$2\sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} x^{2k}=(1+x)^n+(1-x)^n$$ this can be simplified to $$C(n)=3^n+2(-1)^n\>2^{n+1} +1\ .$$ The conjectured recurrence for the $C(n)$ can now be verified a posteriori. It would be nice to have a "direct" proof of it.

share|improve this answer
    
Sorry for my understanding, what is $x_i$? –  Golbez Jan 17 '13 at 14:35
    
I understand, thank you for your reply! –  Golbez Jan 17 '13 at 14:40
    
By Bionomial theorem,(1+x)^n+(1-x)^n=2S,where S is the sum of c*x^{2n}, and thus done. your answer gives me a method to evaluate more results, thank you ! –  Golbez Jan 17 '13 at 18:09
    
@Christian: I added an answer that uses your graph to derive two simpler recurrences which together determine $C(n)$. Presumably the single third-order recurrence can also be derived from those equations, but it's not immediately obvious to me how. –  joriki Jan 21 '13 at 13:14

Let $a_n$, $b_n$, $c_n$ and $d_n$ denote the numbers of paths in Christian's graph that begin at $01$ and end at $20$, $02$, $01$ and $10$, respectively. (By symmetry, $a_n$ and $b_n$ are also the numbers of paths that begin at $01$ and end at $12$ and $21$, respectively.) Extending the paths by one edge yields the following recurrences for $n\ge1$:

$$ a_n=a_{n-1}+b_{n-1}+c_{n-1}\;,\\ b_n=a_{n-1}+b_{n-1}+d_{n-1}\;,\\ c_n=a_{n-1}+a_{n-1}+d_{n-1}\;,\\ d_n=b_{n-1}+b_{n-1}+c_{n-1}\;. $$

The sum of the first two right-hand sides is equal to the sum of the last two right-hand sides, so $a_n+b_n=c_n+d_n=:f_n$ for $n\ge1$; then either sum yields $f_n=3f_{n-1}$ for $n\ge2$.

Subtracting the second equation from the first yields $a_n-b_n=c_{n-1}-d_{n-1}$ for $n\ge1$, and then subtracting the fourth from the third and substituting for $a_{n-1}-b_{n-1}$ yields $g_n=-g_{n-1}+2g_{n-2}$ for $n\ge2$, with $g_n:=c_n-d_n$.

With $a_0=0$, $b_0=0$, $c_0=1$, $d_0=0$ and $a_1=1$, $b_1=0$, $c_1=0$, $d_1=1$ the initial values are $f_1=1$, $g_0=1$, $g_1=-1$, and the recurrences can be solved by the method applied in my other answer. The result is $3f_n=3^n$ and $3g_n=1-(-2)^{n+1}$, and so

$$C(n)=6c_n=3(f_n+g_n)=3^n-(-2)^{n+1}+1\;.$$

share|improve this answer
    
Thanj=ks you for your answer! –  Golbez Jan 23 '13 at 10:22

The standard method for solving such a recurrence is to make the ansatz $C(n)=\lambda^n$ and solve the resulting characteristic equation, $\lambda^3-2\lambda^2-5\lambda+6=0$. The solution $\lambda=1$ can be guessed and factored out, leaving $\lambda^2-\lambda-6=0$ with solutions $\lambda=-2$ and $\lambda=3$. The general solution is then obtained as a linear superposition of these solutions, $C(n)=c_1+c_2(-2)^n+c_33^n$. Your initial values yield a system of linear equations,

$$ \begin{align} c_1-8c_2+27c_3=12\;,\\ c_1+16c_2+81c_3=114\;,\\ c_1-32c_2+243c_3=180\;, \end{align} $$

with solution $c_1=1$, $c_2=2$, $c_3=1$. Thus the number of colourings is

$$C(n)=1-(-2)^{n+1}+3^n\;.$$

This result is also correct for $n=1$ and $n=2$ (if we interpret the edges from $u_1$ to $u_1$ and $v_1$ to $v_1$ in the case $n=1$ as self-loops preventing the vertices from having any colour at all), so with hindsight the solution of the recurrence could have been simplified by using $C(1)$, $C(2)$ and $C(3)$ as initial values instead.

share|improve this answer
    
Thank you, but how to prove the recurrence equation? –  Golbez Jan 17 '13 at 12:55
    
@Golbez: I added another answer in which I derive two simpler recurrences which together determine $C(n)$. –  joriki Jan 21 '13 at 13:13

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.