# 3 plate dinner problem

Consider n people dining in a circular table. Each of them is ordering one of three plates. What is the probability that no two people sitting next to one another will order the same plate?

I intuitively think that every person except the first one has 2 choices as he cannot order the same as the one preceding him. However i can't figure out what happens with the last person as he can have either 1 or 2 choices depending whether the person before him had chosen the same dinner as the first person.

You are considering problem when people are sitting in a line. This is a good idea, but it is not enough to compute probability that it is possible to make a circle from this line. When is it possible? If and only if the last of $n$ people has chosen plate different with previous one and the first one. So we need to compute two sequences: $f_k$ is a probability that $k$ people sitting in the line has ordered plates different for each pair of neighbors and the last one has ordered different plate with the first one, $g_n$ is a probability that $k$ people sitting in the line has ordered plates different for each pair of neighbors and the last one has ordered the same plate as the first one. Then $$f_1 = 0,\\ g_1 = 1,\\ f_k = \frac{f_{k - 1} + 2g_{k - 1}}{3} \text{ for } k > 1,\\ g_k = \frac{f_{k - 1}}{3} \text{ for } k > 1.$$ Substituting last into penultimate we get: $$f_k = \frac{3f_{k - 1} + 2f_{k - 2}}{9} \text{ for } k > 2.$$
EDIT. So $$f_k = \frac23\left(\left(\frac23\right)^{k - 1} - \left(-\frac13\right)^{k - 1}\right) = \frac{2^k + 2\cdot (-1)^k}{3^k}$$ is the answer for you problem when $k \ge 2$ people are sitting at the table. For $k = 1$ the answer depends on whether this man is next to himself or not.
• the final formula is off by one, it's $f_{k+1}$ – mercio Feb 20 '17 at 14:47
• shouldn't it be $f_k=(2^k - 2*(-1)^k)/3^k$ – TheNotoriousSc Feb 20 '17 at 15:09
• mercio, TheNotoriousSc, thanks, fixed. Sign near $(-1)^k$ is correct, you can check for small $k$. – Smylic Feb 20 '17 at 15:35
• The shorter way to get the same answer is appealing to chromatic polynomial of graph $C_n$ that equals to $(x - 1)^n + (-1)^n (x - 1)$ and is the number of proper coloring vertices of $C_n$ in to $x$ colors. So we have $\left.(x - 1)^n + (-1)^n (x - 1)\right|_{x = 3} = 2^n + 2(-1)^n$ is the number of desired orderings of plates and $3^n$ is the total number of orderings of plates, then the answer is $\frac{2^n + 2(-1)^n}{3^n}$. – Smylic Feb 20 '17 at 17:14