1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ OP, I've noticed that you are new on this site and that you've asked some questions to which people have provided you with extensive answers. It is considered common courtesy on this site to say "thank you" by upvoting an answer (by clicking on the uparrow next to it), and to indicate that you find an answer satisfactory by clicking on the check mark next to it. $\endgroup$ – Evan Aad Oct 10 '16 at 6:05
  • $\begingroup$ Thank you very much! I have just seen the answer. I tried casting an upvote but something popped up saying "Votes cast by those with less than 15 reputations are recorded, but do not change the publicly displayed score". Also, your answer looks very neat and well explained. Thank you for helping! :) $\endgroup$ – Anonymous Oct 10 '16 at 13:17
  • $\begingroup$ Thanks for your kind words. I wasn't aware of the restriction on the ability to cast up votes. What about clicking the check mark next to the answer? Do you get the message in that case too? $\endgroup$ – Evan Aad Oct 10 '16 at 13:58
  • 1
    $\begingroup$ yay! :) now it worked! $\endgroup$ – Anonymous Oct 10 '16 at 19:08
  • 1
    $\begingroup$ It is extremely rude to vandalize your question. People put work into writing answers. We hope this site will be a resource in the future for others who may have similar questions. The searching is difficult, but can be done. Please leave the question there so it can be found. $\endgroup$ – Ross Millikan Oct 11 '16 at 3:36
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.