# Three groups at a round table, with adjacent and opposite seats held by differing groups

There are $n$ distinct seats provided around a round table and people from three different groups are invited to a party. However, no two individuals of the same group can seat beside each other or across each other ($n$ is an even number). How many distinct ways can the groups be assigned to seats?

I have calculated a few cases. For $n=2$, the answer is 6:

1---2    2---1
1---3    3---1
2---3    3---2


For $n=4$, the answer is 0, while for $n=6$ it is 42. I have tried every method I know to get a general formula and failed.

• If the table is round isn't there only 2 possibility for $n=2$? I mean group 1 and group 2, group 2 and group 1 are the same solution no?
– wece
Oct 11 '16 at 13:17

The problem is equivalent to counting the number of 3-colourings of the Möbius ladder $M_n$ (here I use the convention that $n$ denotes the number of pairs of vertices; the $n$ in the question becomes $n/2$ in my convention). This problem was solved in 1972 by Biggs, Damerell and Sands:
The paper is now open-access, so be sure to read it. On page 128 they state that the chromatic polynomial that gives the number of $k$-colourings of $M_n$ is $$C(M_n,k)=(k^2-3k+3)^n+(k-1)((3-k)^n-(1-k)^n)-1$$ In particular, when $k=3$ the formula simplifies to $$f(n)=C(M_n,3)=3^n+(-2)^{n+1}-1$$ and this is the answer to the question. I calculate a few values below. \begin{align} f(1)&=6\\f(2)&=0\\f(3)&=42\\ f(4)&=48\\f(5)&=306\\f(6)&=600\\ f(7)&=2442\\f(8)&=6048\end{align}