How many ways can $2n$ dancers line up (n men & n women, who were partnered up), with no partners next to one another?

Question

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?

Answer 1

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} $$

Answer 2

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