1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Okay, but now you only calculated the number of possibilities for which none of them may sit together. That does not calculate what the question asked for, that is where I get confused. Am I missing something? $\endgroup$ – 0rka Jan 23 '18 at 17:25
  • $\begingroup$ $|A_1 \cup A_2 \cup A_3|$ is the number of ways at least one pair is sitting together. Is your question about the part where I explained why we cannot find the complement so easy? $\endgroup$ – ArsenBerk Jan 23 '18 at 17:28
  • $\begingroup$ The problem is $|A_1 \cup A_2 \cup A_3| = |\overline{A_1 \cap A_2 \cap A_3}| \neq | \overline{A_1}| \cap | \overline{A_2}| \cap | \overline{A_3}|$. $\endgroup$ – ArsenBerk Jan 23 '18 at 17:38
  • $\begingroup$ Okay, I thought about it some more and I get it now. In my mind, the way to use inclusion/exclusion was as if each $A_i$ was each couple not sitting next to each other. I wansn't thinking correctly. Thanks for the great explanation! $\endgroup$ – 0rka Jan 23 '18 at 17:41
  • $\begingroup$ No, what is in your mind is correct and mathematically, it is represented by $|\overline{A_1 \cap A_2 \cap A_3}|$. Before explaining Inclusion-Exclusion Principle in my answer, I explained why it is not easy to find the size of the complement directly. If it was easier to find, I would have suggested a method by calculating the size of complement. $\endgroup$ – ArsenBerk Jan 23 '18 at 17:44

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.