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?

  • $\begingroup$ Reminds me a bit of derangements. $\endgroup$ Dec 13 '14 at 1:05
  • $\begingroup$ 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. $\endgroup$ Dec 13 '14 at 1:09
  • $\begingroup$ 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. $\endgroup$ 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\%$

  • $\begingroup$ Brendan also provided this link $\endgroup$
    – Asinomás
    Dec 13 '14 at 2:50
  • 1
    $\begingroup$ The original published solution (in French) to the question is available here: hdl.handle.net/2027/uc1.$b415091?urlappend=%3Bseq=129 . The solution begins at the very bottom of the linked page. $\endgroup$
    – Steve Kass
    Dec 13 '14 at 3:20
  • $\begingroup$ It won't let me see it. $\endgroup$
    – Asinomás
    Dec 13 '14 at 3:34
  • $\begingroup$ Jorge: The document is tagged “Public Domain in the U.S.” I’m not sure I should post a copy here, but email me and I can send you the pages. My email is visible at the upper right of my website (which is in my Stackexchange profile). $\endgroup$
    – Steve Kass
    Dec 13 '14 at 3:38

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.