1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – wece
    Oct 11 '16 at 13:17
1
$\begingroup$

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:

Biggs, N. L.; Damerell, R. M.; Sands, D. A. (1972). "Recursive families of graphs". Journal of Combinatorial Theory. Series B. 12: 123–131.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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