Counting problem involving inclusion-exclusion principle

Question

We're given the following problem:

"The number of arrangements where no wife is sitting next to her husband when three married couples are seated together in the cinema (occupying six consecutive seats) is n. Find n."

Here's my approach. I first counted the number of ways a husband and a wife can sit together while making sure that the reaming people do not sit as couples. So, for the sake analogy, I imagined the follwoing: $$M_1\ M_2 \ \ A_1\ A_2 \ \ B_1 \ B_2$$ where $M_1$ and $M_2$ is the couple that will sit together.

The number of ways the couple can sit together (given that $6$ seats are available) is $3 \cdot2$ because they can be together in $3$ ways, and both of them can switch places (hence the $2$). After this, we have to sit $A_1$ and $A_2$ among the remaining $4$ chairs. This can be done in $4 \cdot 2 \cdot 2$, since $A_1$ can sit in $4$ places, and $A_2$ can sit in $2$ places (since $A_2$ cannot be next to $A_1$) (and since they can switch place, we multiply by $2$ again). Then for $B_1$ and $B_2$ , there is only two sears left, which they can sit in $2$ ways. Multiplying all this together game me $192$.

Then, I counted the number of ways two couple can sit together (making sure the thrid couple would not). In a similar way, I found that it was $48$

Thus, we find that $n=192+48 = 240$ which is correct.

The problem is, now that I think about it, is that when I counted the number of ways the couple could sit together while making sure the rest of the couples do not, I did count (I think) the following: $$A_1B_1B_2A_2M_1M_2$$ where there is actually two couples sitting together (this configuration is just an example, there are few others like this one). So how come I found the correct result? (I'm asking this because my approach seems bizarre while re-reading it).

Also, we were given a hint to solve this problem using the inclusion-exclusion, and I don't know how I'm supposed to do this (which is why I tried an intuitive approach).

Answer 1

There are $6!$ ways to sit six people in a row. From these arrangements, we must remove those in which one or more couples sit together.

A couple sits together: There are $\binom{3}{1}$ ways to choose a couple that sits together. We now have five objects to arrange, the couple and the other four people. They can be arranged in $5!$ ways. The couple can be arranged internally in $2!$ ways. Hence, there are $$\binom{3}{1}5!2!$$ such seating arrangements.

However, we have subtracted too much. We have subtracted each case in which two couples sit together twice, once for each way we could designate one of the couples as the couple that sits together. Since we only want to subtract them once, we need to add those arrangements back.

Two couples in which the members of each couple sit together: There are $\binom{3}{2}$ to choose two couples in which the members of each couple sit together. This gives us four objects to arrange, the two couples and the other two people. The objects can be arranged in $4!$ ways. Each couple can be arranged internally in $2!$ ways. Hence, there are $$\binom{3}{2}4!2!^2$$ such seating arrangements.

Now, we have added too much. We subtracted those arrangements in which all three couples sit together three times, once for each way we could have designated one of the couples as the couple that sits together, and added them three times, once for each of the $\binom{3}{2}$ ways we could designate two of the couples as the ones that sit together. Therefore, we have not excluded such arrangements, so we need to subtract them from the total.

Three couples in which the members of each couple sit together: There are three objects to arrange, namely the couples. The objects can be arranged in $3!$ orders. Each couple can be arranged internally in $2!$ ways. Hence, there are $$\binom{3}{3}2!^3$$ such seating arrangements.

By the Inclusion-Exclusion Principle, the number of permissible seating arrangements is $$6! - \binom{3}{1}5!2! + \binom{3}{2}4!2!^2 - \binom{3}{3}3!2!^3$$