Find the number of ways of arranging n couples $\{H_i,W_i\}$, $i=1,2,…,n,$ in a row such that $\{H_i\}$ is not adjacent to $\{W_i\}$ for each $i=1,2,…,n$.
I have included part of the solution to the question.
An arrangement in $S$ satisfies the property $P_i$, where $i=1,2,…,n,$ if and only if $H_i$ and $W_i$ are adjacent.
$\omega(1) = \sum_{i=1}^{n} \omega(P_i) = \binom{n}{1}(2)(2n-1)!$
My question is about the above statement. I don't understand why finding $\omega(1)$, which is the number of arrangements where only one couple is adjacent, is given by $\binom{n}{1}(2)(2n-1)!$.
I do understand that there are (2n−1)! ways to arrange the remaining people after choosing a couple $\binom{n}{1}$ and that they can be permutated in $2!$ ways. But I don't see why the (2n−1)! would ensure that the rest of the couples won't be adjacent.
Best Answer
I expect that it doesn't ensure the rest of the couples won't be adjacent, in fact quite the contrary, it ignores it.
A good approach to this problem would be inclusion-exclusion. Using the notation already started above, $\omega(1)$ can be interpreted as the number of permutations which have the condition similar to "at least one husband-wife pair are sitting next to one another" (however we will have overcounted and will need to compensate)
A likely follow up so we can compensate the overcounting before using the notation already started would be to calculate $\omega(2) = \sum_{i<j} P_i\cap P_j$, the number of permutations where at least 2 husband-wife pairs sit next to one another (again, with potential overcounting).
Continuing on to calculate $\omega(3), \omega(4),\dots$ by the inclusion exclusion principle, the number of permutations where no husband-wife pair sit next to one another is:
$$\sum_{i=0}^n (-1)^i \omega(i)$$
Note, $\omega(0) = (2n)! = $number of permutations ignoring restrictions.
http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle
To calculate $\omega(i)$ for arbitrary $i$, it is $\sum_{k_1<k_2<\dots<k_i} (P_{k_1}\cap P_{k_2}\cap\dots\cap P_{k_i})~~$ where each $k_j$ is a number from $1,2,\dots,n~~~$ (note, that in a more common notation, this would be $i$ number of $\sum$ symbols appearing in a row. the benefit of writing limits as $k_1<k_2<\dots<k_i$ is that I can use a single sigma)
In a more usable form, $\omega(i) = \binom{n}{i}2^i(2n-i)!$
$\omega(i)$ is calculated exactly how you had for $\omega(1)$ for the same reasons. The $\binom{n}{i}$ term selects which of the $n$ husband-wife pairs you designate to be guaranteed to sit adjacent to one another, the $2^i$ term is to decide for each of those guaranteed husband-wife pairs whether the husband sits on the left of the wife or to the right of the wife, and the $(2n-i)!$ term is to permute the either pairs we designated to be together or individuals who we haven't yet designated to be together. You can think of it as permuting the husbands of the pairs chosen along with the husbands and wives of those we haven't chosen, after having done so we squeeze the wives of those chosen husbands into seats next to them and push everyone down the bench to make room as needed.
Thus for a final answer, $\sum\limits_{i=0}^n((-2)^i\binom{n}{i}(2n-i)!)$