How to solve probability circular table problem with neighbors.

7 people are seated around a round table eating dinner. They then all get up, get dessert and then sit down at random. What is the probability that each person has two new neighbors? What is the answer to this question if there are 8 people? How about for 9 people?

• Reminds me a bit of derangements. Dec 13 '14 at 1:05
• On of the differences between this and derangements is that here we should treat the places at the table as indistinguishable; otherwise we're adding an extra complication to the problem that doesn't help. Dec 13 '14 at 1:09
• I think there are a few possibilities for six. For example, if the people are at the vertices of a hexagon $ABCDEF$, switch $A$ and $C$, and switch $B$ and $E$. Then no initial neighbors are still neighbors. I think the probability is $0$ for five people. EDIT: An approach involving recursion seems promising ... starting with the number of ways to arrange the six people, and imagining adding a seventh person. Dec 13 '14 at 1:19

Consider the graph $K_5$, there is a bijection between the valid arrangements and the hamiltonian cycles contained by $K_5$ after substracting the edges of a hamiltonian cycle of $K_5$. Let $Q_n$ be that number.
Thanks to the help of mathoverflow (Brendan McKay) I now know $Q_n$ is given by this sequence. On the other hand there are clearly $(n-1)!$ cycles in $K_n$ total, thus what we want is $\frac{Q_n}{(n-1)!}$.Since $Q_7=23$ the probability is $\frac{23}{6!}\approx3.2\%$