3
$\begingroup$

Three married couples have bought $6$ seats in a row for a concert. How many ways can they be seated if no man sits next to his wife.

I have worked through this problem and have got the correct answer. The problem I am having is, I can't, for the life of me, wrap my head around how to find the number of ways $1$ couple sits together.

$6!$ ways to order everyone $= 720$

All couples sit together: $3!(2!)^3=48$. Three different couples can be orientated $3!$ ways and each couple can be orientated $2!$ ways. Makes perfect sense to me.

Two couples sit together: $3(3)(2!)^4=144$. Pick which couple won't sit together, $3$. There are $3$ ways they cannot sit together and $2!$ ways to order them. $2!$ ways to order the remaining two couples and $2!$ ways to order which seat man or wife takes for both of them. Okay, great, I got that.

One couple sits together: I fumbled around with this until I came up with the $288$ I needed to get the correct answer: $3(2!)^2(4!)$. But, I have absolutely no idea how to make sense of it as I did above for the other possibilities. Pick a couple, $3$, order them $2!$. Pick a second couple $2$, then next to him can't be his wife, but it can be any of the other $3$. That gives you the $3(2!)^2$ and $3$. But we still need $4$ and $2$ of the $4!$. I can't reason out how we get to that conclusion.

Final answer: $720-48-144-288=240$. There are $240$ ways for no couple to sit together.

If someone could please break it down, Barney style, how one couple sitting together must be ordered it would be fantastic. I'm having a serious mental block.

$\endgroup$
1
$\begingroup$

You could do it this way.

  • Couple sits at the end, so the arrangement must be $X_1X_2Y_1Z_1Y_2Z_2$. The number of choices for the six people, going left to right, are $6,1,4,2,1,1$, total $48$.
  • One away from the end: $Y_1X_1X_2Z_1Y_2Z_2$, choices $6,4,1,2,1,1$, total $48$.
  • Sitting in the middle: $Y_1Z_1X_1X_2(any)(any)$, choices $6,4,2,1,2,1$, total $96$.
  • The reverse of the first two cases, total $96$.

This gives your $288$.


If you wanted, you could instead do the whole thing by inclusion/exclusion. Let $A_1$ be the set of arrangements in which the first couple sit together, $A_2$ and $A_3$ likewise. Then the number we need is $$\eqalign{|\overline A_1\cap\overline A_2\cap\overline A_3| &=|{\cal U}|-|A_1\cup A_2\cup A_3|\cr &=|{\cal U}|-|A_1|-|A_2|-|A_3|+|A_1\cap A_2|+|A_1\cap A_3|\cr &\qquad\qquad\qquad\qquad\qquad\qquad{}+|A_2\cap A_3|-|A_1\cap A_2\cap A_3|\ .\cr}$$ The total number of arrangements of $6$ people is $6!\,$. To count $A_1$,

  • pick the places for the first couple to sit: as they are sitting together, this amounts to arranging the letters $PPPPC$, where $P$ is a person and $C$ is a couple. . . . . there are $5$ ways to do this;
  • pick which way round the members of the couple sit. . . . . $2$ ways;
  • order the other $4$ people. . . . . $4!$ ways.

So $|A_1|=5\times2\times4!\,$, and clearly $|A_2|,|A_3|$ are the same. For similar reasons, starting by ordering $PPC_1C_2$ we have $$|A_1\cap A_2|=P(4,2)\times2^2\times2!\ ,\quad |A_1\cap A_2\cap A_3|=3!\times2^3$$ and so our answer is $$6!-3\times5\times2\times4!+3\times P(4,2)\times2^2\times2!-3!\times2^3 =6!-6!+288-48=240\ .$$

$\endgroup$
  • $\begingroup$ I 'think' that I may finally be there with my understanding of $1$ couple sits together now, thanks! $\endgroup$ – Vincent Jun 17 '14 at 17:51
0
$\begingroup$

It will be difficult if you are trying for the number of ways that exactly one couple will sit together. The way of using the principle of inclusion-exclusion is described in another question and also here.

So, the number of ways that $n$ couples will not have a single couple sitting next to each other will be:

$$ (2n)! - \sum_{i=1}^n (-1)^{i+1} 2^i \binom{n}{i} (2n-i)! $$

$\endgroup$

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.