Number of possibilities to seat $3$ pairs of husbands and wives so that at least one husband and wife sit together

171 Views Asked by At

Question: There are $6$ people that consist of $3$ sets of husbands and wives. How many possibilities are there to seat all of them on a bench if at least one couple sits next to each other?

Initially, I thought I could just subtract from the total number of possibilities to seat $6$ people which is $6!$, the complement of the question which is "How many possibilities are there to seat those same people where no couple sits next to each other?". To evaluate how many possibilities there are for the complement, I'll have to first seat all three women on the bench. There are ${{6}\choose{3}} \cdot 3!$ ways to do it. Next, I'll have to seat the guys accordingly (so neither of them sits next to their spouse). The number of possibilities to seat each of them is exactly $2$, thus resulting in $2^{3}$ possibilities for the three of them.

So according to my calculation, the total number of possibilities is: $$6! - {{6}\choose{3}} \cdot 2^{3} = 560$$

However, after comparing my answer to what is written in the textbook, the answer should be: $$3 \cdot 2 \cdot 5! - 3 \cdot 2^{2} \cdot 4! + 2^{3} \cdot 3! = 480$$ Looks like the textbook's answer uses inclusion/exclusion. Before comparing my answer to the textbook's one, I was certain that inclusion/exclusion was unnecessary (I still do in fact), because there was only one exclusion to make - the complement (which I've described above). I really don't get why someone would apply this principle here. Clarifications on the matter will greatly appreciated.

1

There are 1 best solutions below

7
On BEST ANSWER

Finding the complement is not so easy. For example assuming $3$ women is sitting together (by together I mean between them there is no men), for the women in middle, the condition for the complement already satisfied. So your calculation must change in this case and this is not the only case where your calculation must change (For example if one of the women is on the leftmost place and there is a woman in right of her, then the woman on the leftmost side also satisfies the condition for complement and obviously, number of ways are different for these two cases).

Instead, you can use Inclusion-Exclusion Principle by considering the events $A_1, A_2, A_3$ where $A_i$ is the event that $i^{th}$ couple is sitting together. So we have to find $$|A_1 \cup A_2 \cup A_3| = 3|A_1|-3|A_1 \cap A_2|+|A_1 \cap A_2 \cap A_3|$$ since $|A_1| = |A_2| = |A_3|$ and $|A_1 \cap A_2| = |A_1 \cap A_3| = |A_2 \cap A_3|$ by renumbering.

Now, we have $|A_1| = 2! \cdot 5!$ (because first pair is sticked so we have $5$ things to permute with $5!$ and we can switch the man and woman with $2!$), $|A_1 \cap A_2| = 2^2 \cdot 4!$ and $|A_1 \cap A_2 \cap A_3| = 2^3 \cdot 3!$ by similar arguments. So the result follows.