inclusion-exclusion problem - sitting arrangement

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.
• A solution is posted here. – N. F. Taussig May 4 '18 at 0:08
• unfortunately, that only confused me. @N.F.Taussig – Subin Park May 8 '18 at 2:19
• Why don't you see the reference mentioned there? In summary, if $f(n,k)$ denotes the number of ways of selecting $k$ objects, no two consecutive, from $n$ objects arranged in a row (not a circle), then $f(n,k) = \binom{n-k+1}{k}.$ (Easy recurrence formula with $f(n,1)=n,$ $f(n,n )=0$ and $f(n,k) = f(n-1,k)+f(n-2,k-1)$. We also could show $d_k = f(2n-1,k)+f(2n-3,k-1) = \frac{2n}{2n-k}\binom{2n-k}{k}$ dividing cases. Both formulae come from dividing cases by whether the selections contain the first element or not. – Kanu Kim May 14 '18 at 7:26
• I found someone already answered: math.stackexchange.com/questions/2772732/… – Kanu Kim May 14 '18 at 8:06

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)!$