How many ways can $2n$ dancers line up (n men & n women, who were partnered up), with no partners next to one another? There are n men and n women, who are partnered up to dance together for a performance. At the end of the performance, they line up to take a bow. How many ways is it possible for these $2n$ people to line up in a row, such that no man/woman is standing next to his/her partner?
 A: As you noted, the inclusion/exclusion principle will come in handy here.
Set $N := \{1, 2, \dots, n\}$, denote the group of men by $M$ and the group of women by $W$, and set $G:=M\cup W$.
Enumerate the members of $M$: $(m_1, m_2, \dots, m_n)$. For every $i \in N$ denote by $w_i$ the woman who's partnered with $m_i$, and set $P_i := \{m_i, w_i\}$.
Denote by $Z$ the set of all possible orderings of the members of $G$ in a row. For every $i \in N$ denote by $Z_i$ the set of all $z \in Z$ in which the members of the pair $P_i$ stand next to each other.
Using this notation, we are required to compute $\left|\overline{Z_1}\ \overline{Z_2}\cdots\overline{Z_n}\right|$, where complements are taken w.r.t. $Z$, and where multiplication of sets stands for their intersection, and addition of sets stands for their union.
We have
$$
\begin{align}
\left|\overline{Z_1}\ \overline{Z_2}\cdots\overline{Z_n}\right| &\overset{\text{De Morgan}}{=} \left|\overline{Z_1 + Z_2 + \cdots Z_n}\right| \\
&= |Z| - \left|Z_1 + Z_2 + \cdots + Z_n\right| \\
&= (2n)! - \left|Z_1 + Z_2 + \cdots + Z_n\right| \\
&\overset{\text{Incl./Excl.}}{=} (2n)! - \sum_{k = 1}^n (-1)^{k+1} \sum_{I \subseteq N\ |:\ |I| = k} \left|\prod_{i \in I} Z_i\right| \\
&\overset{\text{symmetry}}{=} (2n)! - \sum_{k = 1}^n(-1)^{k+1}\binom{n}{k}\left|Z_1Z_2\cdots Z_k\right|.
\end{align}
$$
So all that remains is to compute $\left|Z_1Z_2\cdots Z_k\right|$ for every $k \in N$. Let $k \in N$.


*

*Thinking of the pairs $P_1, P_2, \dots, P_k$ as indivisible units and thowing the remaining $2n-2k$ members of $G$ to the mix, there are $\left(k + (2n-2k)\right)! = (2n-k)!$ ways in which this bunch can be ordered.

*For each such permutation there are $2^k$ ways in which $m_i$ and $w_i$ can stand w.r.t. each other, for every $i \in \{1, 2, \dots, k\}$.
To sum up,
$$
\left|Z_1Z_2\cdots Z_k\right| = 2^k(2n-k)!,
$$
and therefore
$$
\begin{align}
\left|\overline{Z_1}\ \overline{Z_2}\cdots\overline{Z_n}\right| &= (2n)! - \sum_{k = 1}^n(-1)^{k+1}\binom{n}{k}2^k(2n-k)!.
\end{align}
$$
A: Let the pairs be $P_1,\ldots,P_n$. For $k\in[n]$ let $A_k$ be the set of lineups in which the members of $P_k$ are adjacent. If $\varnothing\ne I\subseteq[n]$, then
$$\left|\bigcap_{k\in I}A_k\right|=2^k(2n-k)!\;:$$
we treat each of the pairs $P_k$ with $k\in I$ as a single entity, so there are $2n-k$ entities in the lineup, and each of the pairs $P_k$ with $k\in I$ has two possible ‘states’. Thus,
$$\begin{align*}
\left|\bigcup_{k\in[n]}|A_k\right|&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}\left|\bigcap_{k\in I}A_k\right|\\
&=\sum_{k=1}^n(-1)^{k+1}\binom{n}k2^k(2n-k)!\;.
\end{align*}$$
This is the number of unacceptable lineups, so the number of acceptable lineups is
$$\begin{align*}
(2n)!-\sum_{k=1}^n(-1)^{k+1}\binom{n}k2^k(2n-k)!&=(2n)!+\sum_{k=1}^n(-1)^k\binom{n}k2^k(2n-k)!\\
&=\sum_{k=0}^n(-1)^k\binom{n}k2^k(2n-k)!\;,
\end{align*}$$
and if $n\ge 2$ this reduces to
$$\sum_{k=2}^n(-1)^k\binom{n}k2^k(2n-k)!\;,$$
since the first two terms are $(2n)!$ and $-n\cdot2\cdot(2n-1)!=-(2n)!$.
