A group of $n$ couples (a total of $2n$ people) sit at a circular table. Arrangements that differ by any rotation of the seating positions are considered to be the same. Find a formula for the number of seatings where no woman sits beside her partner?

  • $\begingroup$ By complement, we find the number of seating where there are one couples sits together. We choose one couples from n couple and fixed them at two seats. So, the number to arrange is 2(2n-2)!. So, we can find the number of seating where no woman sits beside her partner are (2n-1)!-2(2n-2)!= (2n-3)*(2n-2)!. $\endgroup$ – Worawit Tepsan Oct 31 '13 at 6:31

This can be solved using inclusion-exclusion. We have $n$ conditions for the $n$ couples sitting next to each other. If one of the conditions is fulfilled, we can regard the corresponding couple as a single person to be seated and include a factor $2$ for the two orders in which the couple can sit. So there are $2^k(2n-k-1)!$ different arrangements that satisfy $k$ particular conditions, and thus

$$ \sum_{k=0}^n\binom nk(-1)^k2^k(2n-k-1)! $$

different arrangements that satisfy none of the conditions. This is OEIS sequence A129348.


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.