I am not sure how to approach this question.
How many ways are there to seat n couples around a circular table such that no couple sits next to each other?
Since it's a part of inclusion-exclusion, I'm supposed to use that method. But I have no clue how to approach this. I know total number of people are 2n and that's about it. I've looked at other stack exchange questions on the same exact problem but none of them helped...
- So I looked at the Menage problem, but that's seriously confusing - it's worse than other Mathexchange answers. In the solution, it mentions $d_k = (2n/2n-k) * C(2n-k,k) $. I have no clue where this guy came from.
Here's how a straightforward application of inclusion-exclusion would go:
First you count the ways that you can seat the people with no strings attached. That's $(2n)!$ (or $(2n-1)!$ if you're discounting rotations; I'm not sure if you are or not, so I'll assume you're not, but it just affects all the answers by a factor of $2n$)
Then you exclude the ways you can seat the people with one couple together. That's $2 \cdot (2n-1)!$; $2$ ways to seat the couple once their location has been determined, and $(2n-1)!$ ways to seat $2n-2$ people and $1$ couple around the table (counting the couple as one object, since they must sit together). There are $n$ couples, so you'll subtract $n \cdot 2 \cdot (2n-1)!$
Then you re-include the ways you can seat the people with two couples together. That's $2^2 \cdot (2n-2)!$: $2^2$ ways to seat the two couples once their locations have been determined, and $(2n-2)!$ ways to seat $2n-4$ people and $2$ couples. There are $\binom n2$ couples so you'll add back $\binom n2 \cdot 2^2 \cdot (2n-2)!$
Etc.