Formula about relaxed ménage problem I was reading about relaxed ménage problem on this page:

The relaxed ménage problem asks for the number  of $m_n$ ways of seating  couples around a circular table, so that no one sits next to his or her partner. This is nearly the same as the ménage problem, only now we have relaxed the requirement that men and women alternate.
To determine $m_n$ , we begin with the set $S$ of all $\left(2n\right)!$ ways of seating the  individuals around the table, and use inclusion-exclusion on the set of couples who end up sitting together. Let us call the elements of $S$  seatings, and let us denote by $w_k$ the number of seatings under which some specified set of $k$ couples (and possibly some other couples) end up sitting together. Clearly $w_k$,  does not depend on the particular set of $k$ couples we choose, and so, by the principle of inclusion and exclusion, we have:

$$m_{n}=\sum_{k=0}^{n}\left(-1\right)^{k}\binom{n}{k}w_{k}$$

I don't know how the principle of inclusion and exclusion has been used here,so can someone please derive the formula and explain where does it come from?
 A: The general information about inclusion-exclusion principle can be found here. Below I will reproduce the most essential points important for understanding the particular problem.
In general the inclusion-exclusion principle states that for finite sets $A_1,\dots, A_n$, one has the identity:
$$\left|\bigcup_{i=1}^n A_i\right| = \sum_{i=1}^n |A_i| - \sum_{1 \leqslant i < j \leqslant n} |A_i\cap A_j| + \sum_{1 \leqslant i < j < k \leqslant n} |A_i \cap A_j\cap A_k| - \cdots + (-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|.$$
In the applications it is common to see the principle expressed in its complementary form. That is, letting $S$ be a finite universal set containing all of the $A_i$ and letting $\bar A_{i}$ denote the complement of $A_i$ in $S$:
$$\left|\bigcap_{i=1}^n \bar{A_i}\right| = \left|S\setminus\bigcup_{i=1}^n A_i \right| =|S| - \sum_{i=1}^n |A_i| + \sum_{1 \leqslant i < j \leqslant n} |A_i\cap A_j| - \cdots + (-1)^n |A_1\cap\cdots\cap A_n|.\tag1$$
If the size, $w_k$, of the intersection sets  appearing in the formula (1) depends only on the number of sets, $k$, in the intersections (i.e. $\forall i:\, |A_i|=w_1,\; \forall i<j:\, |A_i\cap A_j|\equiv w_2$, and so on), the expression can be simplified to:
$$
\left|\bigcap_{i=1}^n \bar{A_i}\right|  =\sum_{k=0}^n (-1)^{k}\binom nk w_k.
$$
This is exactly the case in the considered problem, with $A_i$ being the set of all permutations with $i$-th couple sitting together.
