I am reading through counting exercises for my combinatorics class and this has been stumping me for the past $3$ hours:
I have $4$ married couples $M_1,W_1,M_2,W_2,M_3,W_3,M_4,W_4$ that I need to arrange in seats such that no one sits next to their spouse.
Example: $M_1,M_2,M_3,M_4,W_1,W_2,W_3,W_4$ works but not $M_1,M_2,W_2,M_3,M_4,W_1,W_3,W_4$ since $M_2$ sits next to his spouse $W_2$.
I know there are $8!=40,320$ total arrangements. My strategy is to take that number and then subtract the arrangements where I have all $4$ couples together, exactly $3$ couples together, exactly $2$ couples together, and exactly $1$ couple together. This leaves the number of arrangements with no couples sitting adjacent.
So far I have calculated that there are $4! \cdot 2^4=384$ arrangements with all $4$ couples to be together. This is because there are $4!$ ways to arrange the $4$ couples, and each couple can be seated either $MW$ or $WM$.
For the remainder of the calculations I am stumped. I have tried different ways to count them, but I keep getting duplicates and it seems like there must be an easier way. Am I on the right track or am I completely missing an obvious strategy here?
Best Answer
There are $8!$ ways to arrange eight people in a row. From these, we must subtract those arrangements in which members of a couple sit in adjacent seats.
A couple sits in adjacent seats: We have seven objects to arrange, the couple and the other six people. The objects can be arranged in $7!$ ways. The members of the couple can be arranged in $2!$ ways. Since there are four ways to select the couple, there are $$\binom{4}{1}7!2!$$ such seating arrangements.
However, $8! - \binom{4}{1}7!2! = 0$, so we have subtracted too much since, as your example $$M_1, M_2, M_3, M_4, W_1, W_2, W_3, W_4$$ shows, it is possible to seat the people so that no couple sits together. The reason for this is that we have subtracted each seating arrangement in which there are two couples in which members of a couple sit together twice, once for each way we could have designated one of those couples as the one that sits together. We only want to subtract such arrangements once, so we must add them back.
Two couples in which the members of a couple sit in adjacent seats: We have six objects to arrange, the two couples and the other four individuals. The objects can be arranged in $6!$ ways. The two couples can each be arranged internally in $2!$ ways. There are $\binom{4}{2}$ ways of selecting the two couples. Hence, there are $$\binom{4}{2}6!2!^2$$ such seating arrangements.
Now, we have $8! - \binom{4}{1}7!2! + \binom{4}{2}6!2!^2$. However, we have added too much. We have subtracted arrangements in which there are three couples in which the members of a couple sit together three times, once for each way we could designate one of those couples as the one that sit together, and added them three times, once for each of the $\binom{3}{2}$ ways we could designate two of them as the two that sit together. Thus, we have not subtracted them from the total, as we must.
Three couples in which the members of a couple sit in adjacent seats: We have five objects to arrange, three couples and the other two individuals. The objects can be arranged in $5!$ ways. Each couple can be arranged internally in $2!$ ways. There are $\binom{4}{3}$ ways of selecting the couples in which the members of a couple sit together. Hence, there are $$\binom{4}{3}5!2!^3$$ seating arrangements.
This gives us a running total of $8! - \binom{4}{1}7!2! + \binom{4}{2}6!2!^2 - \binom{4}{3}5!2!^3$. At this point, you should suspect that we have subtracted too much. We have. We have subtracted arrangements in which there are four couples in which the members of a couple sit together four times, once for each way of designating one of those couples as the one that sits together; added them six times, once for each of the $\binom{4}{2}$ ways we could designate two of those couples as the two in which the members of a couple sit together; and subtracted them four more times, once for each of the $\binom{4}{3}$ ways we could designate three of those couples as the three in which the members of a couple sit together. Since we only want to subtract such seating arrangements once, we must add them to the total.
Four couples in which members of a couple sit together: We have four objects to arrange, the couples. They can be arranged in $4!$ ways. Each couple can be arranged in $2!$ ways. Hence, there are $$\binom{4}{4}4!2!^4$$ such seating arrangements.
By the Inclusion-Exclusion Principle, the number of ways the four couples can be seated so that no person sits next to his/her spouse is $$8! - \binom{4}{1}7!2! + \binom{4}{2}6!2!^2 - \binom{4}{3}5!2!^3 + \binom{4}{4}4!2!^4$$