4
$\begingroup$

Six married couples are to be seated at a round table so that men and women alternate. In how many ways can the seating be arranged if nobody wants to sit next to his or her spouse? Two seatings are considered the same if every person’s answer to the question “Who is on your immediate left?” would be the same for both seatings, and every person’s answer to “Who is on your immediate right?” would be the same, as well.

$\endgroup$
0
$\begingroup$

This is related to the Ménage problem.

The solution to that problem for $n = 6$ is $115200$. However you want to count only once two solutions that are the same up to a rotation, so we must divide by $2n = 12$ to get $9600$. So in this case we are looking for this related OEIS sequence A094047.

$\endgroup$
2
  • $\begingroup$ How do I go about proving the formula/proving that it is indeed 9600? $\endgroup$ – user826216 Oct 6 '20 at 15:23
  • $\begingroup$ You need to study the linked Wikipedia page where you can find formulas and references to proofs, and especially Non-sexist solution of the ménage problem by Bogart & Doyle (1986) and The problème des ménages revisited by Kirousis & Kontogeorgiou (2018) which should be simpler proofs (but I am not sure about this). $\endgroup$ – BillyJoe Oct 6 '20 at 16:02

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.