Probabilities Involving 4 Married Couples

[e(ho0n3]

[SOLVED] Probabilities Involving 4 Married Couples

Homework Statement

If 4 married couples are arranged in a row, find the probability that no husband sits next to his wife.

2. The attempt at a solution
I will call a married couple a pair and denote n_i as the number of arrangements, given i pairs, where no husband sits next to his wife. There are two ways that I've thought of for counting n_i:

(a) n_1 is obviously 0. For i = 2, there are 4 ways to pick the first person, 2 ways to pick the second person and 1 way to pick the third and last persons so n_2 = 4 * 2. Now given another pair, I can stick the husband in front of the first person or behind the first, second, third or fourth person. That's 5 choices. The wife can go in any of the remaining 4 choices. Thus, n_3 = 5 * 4 * n_2 = 5 * 4 * 4 * 2. Given yet another pair, using the same reasoning as before n_4 = 7 * 6 * n_3 = 7 * 6 * 5 * 4 * 4 * 2. The only problem with this method, I think, is that it may not take into account that fact that the pairs are distinct.

(b) For i = 4, there are 8 ways to pick the first person. Excluding the spouse of the first person, that leaves 3 pairs of which there are n_3 arrangements. In any of these arrangements, the spouse can behind the first, second, third, ..., or last person, i.e. there are 6 choices for where the spouse could go. Appending one of these arrangements (with the spouse) to the first person produces an arrangement involving 4 pairs. Thus, n_4 = 8 * 6 * n_3. Similarly, n_3 = 6 * 4 * n_2. From (a), n_2 = 4 * 2. Thus, n_4 = 8 * 6 * 6 * 4 * 4 * 2. This method looks more promising. I don't see anything wrong with it.

The probability is n_4 / 8!. In both cases, I get the wrong answer. The right answer according to the book is 12/35.

 

[Skins]

The answer of 12/35 is correct. But how do we arrive at such an obscure beast. I have to admit this one got me a bit puzzled at first. I'll give you an idea of how I worked it out.

Think of the problem in terms of events. I reasoned that we have have 4 couples, I'll label them C1, C2 ,C3 and C4. Next I defined some events. namely

E1 = event that couple C1 sits together
E2 = event that couple C2 sits together
E3 = event that couple C3 sits together
E4 = event that couple C4 sits together.

Now the union of these events E1 U E2 U E3 U E4 will be the event that at least 1 of the 4 couples sit together (why ?). Therefore the probability P(E1 U E2 U E3 U E4) will be the probability that at least one of the 4 couples will sit together.

I will leave the calculation of the probability P(E1 U E2 U E3 U E4) up to you. Once you have properly computed the above probability of at least one married couple sitting together it is a very simple matter to compute the probability that none of the couples will sit together.

One last hint. When calculating P(E1 U E2 U E3 U E4) bear in mind that the events are NOT mutually exclusive (disjoint).

Skins.

 

[e(ho0n3]

I had thought of finding the probability that way but since it gets messy, I was hoping for an easier way.

 

[e(ho0n3]

OK. Here I go. By the inclusion-exclusion identity:

$$\begin{align*}P(E_1 \cup E_2 \cup E_3 \cup E_4) & = P(E_1) + P(E_2) + P(E_3) + P(E_4) \\ & \quad - P(E_1E_2) - P(E_1E_3) - P(E_1E_4) - P(E_2E_3) - P(E_2E_4) - P(E_3E_4) \\ & \quad + P(E_1E_2E_3) + P(E_1E_2E_4) + P(E_1E_3E_4) + P(E_2E_3E_4) \\ & \quad - P(E_1E_2E_3E_4)\end{align*}$$

By symmetry,

$$\begin{align*}P(E_1) &= P(E_2) = P(E_3) = P(E_4) \\ P(E_1E_2) &= P(E_1E_3) = P(E_1E_4) = P(E_2E_3) = P(E_2E_4) = P(E_3E_4) \\ P(E_1E_2E_3) &= P(E_1E_2E_4) = P(E_1E_3E_4) = P(E_2E_3E_4)\end{align*}$$

so the equation reduces down to

$$P(E_1 \cup E_2 \cup E_3 \cup E_4) = 4P(E_1) - 6P(E_1E_2) + 4P(E_1E_2E_3) - P(E_1E_2E_3E_4)$$

Define $f(n)$ as the number of ways to position a couple given $n$ row positions. $f(n) = 2(n-1)$ since the couple may occupy positions 1 & 2, 2 & 3, ..., or $n - 1$ & $n$ and the husband or wife may be on the left.

$P(E_1)$ is easy to determine: there are $f(8)$ ways to position the first couple and 6! ways to position the rest so $P(E_1) = f(8) \cdot 6! / 8! = 1/4$.

Determining $P(E_1E_2)$ is more complicated than $P(E_1)$ since the row positions available to the second couple depend on where the first couple is. In other words,

$$P(E_1E_2) = \sum_{i=1}^7 P(E_1E_2|F_i)$$

where $F_i$ is the event that the first couple occupies row positions $i$ and $i+1$. For $i = 1$, the first couple has two available positions: 1 & 2. The second couple has the rest available: 3, ..., 8. The two couples may be positioned in $f(2)f(5)$ = 20 ways. The rest may be positioned in 4! ways. Thus $P(E_1E_2|F_1) = 20\cdot4! / 8! = 1 / 84$. By symmetry, $P(E_1E_2|F_7) = P(E_1E_2|F_1)$.

Applying the prior argument for the rest of the values of $i$ yields that

$$\begin{align*}P(E_1E_2|F_2) &= P(E_1E_2|F_6) = 16\cdot4! / 8! = 1/105 \\ P(E_1E_2|F_3) &= P(E_1E_2|F_5) = 1/105 \\ P(E_1E_2|F_4) &= 1/105 \end{align*}$$

Putting it all together yields that $P(E_1E_2) = 1/14$.

$P(E_1E_2E_3)$ is found in a similar, but more complicated manner to $P(E_1E_2)$, i.e. the positions available to the third couple depend on where the first and second couple are situated:

$$P(E_1E_2E_3) = \sum_i \sum_j P(E_1E_2E_3|F_iG_j)$$

where $G_j$ represents the event that the second couple occupies positions $j$ and $j+1$, $j > i+1$ or $j < i - 1$.

Let $N_{ij}$ be the number of ways of situating three couples given $F_i$ and $G_j$. The table below shows some values:

$$\begin{tabular}{c|c|l} \(i\) & \(j\) & \(N_{1j}\) \\ \hline 1 & 3 & \(f(2)f(2)f(4) = 24\) \\ 1 & 4 & \(f(2)f(2)(f(1) + f(3)) = 16\) \\ 1 & 5 & \(f(2)f(2)(f(2) + f(2)) = 16\) \\ 1 & 6 & \(f(2)f(2)(f(1) + f(3)) = 16\) \\ 1 & 7 & \(f(2)f(2)f(4) = 24\) \\ 2 & 4 & \(f(2)f(2)(f(1) + f(3)) = 16\) \\ 2 & 5 & \(f(2)f(2)(f(1) + f(1) + f(2)) = 8\) \\ 2 & 6 & \(f(2)f(2)(f(1) + f(2) + f(1)) = 8\) \\ 2 & 7 & \(f(2)f(2)(f(1) + f(3)) = 16\) \\ 3 & 1 & \(f(2)f(2)f(4) = 24\) \\ 3 & 5 & \(f(2)f(2)(f(2) + f(2)) = 16\) \\ 3 & 6 & \(f(2)f(2)(f(2) + f(1) + f(1)) = 8\) \\ 3 & 7 & \(f(2)f(2)(f(2) + f(2)) = 16\) \\ 4 & 1 & \(f(2)f(2)(f(1) + f(3)) = 16\) \\ 4 & 2 & \(f(2)f(2)(f(1) + f(3)) = 16\) \\ 4 & 6 & \(f(2)f(2)(f(3) + f(1)) = 16\) \\ 4 & 7 & \(f(2)f(2)(f(3) + f(1)) = 16\) \\ \end{tabular}$$

Let $N_i$ be the number of ways of situating three couples given $F_i$. The table below summarizes the table above for all values of $i$.

$$\begin{tabular}{c|l} \(i\) & \(N_i\) \\ \hline 1 & 96 \\ 2 & 48 \\ 3 & 64 \\ 4 & 64 \\ 5 & 64 \\ 6 & 48 \\ 7 & 96 \end{tabular}$$

where by symmetry, $N_i$ for $i=5,6,7$ are the same for $i=3,2,1$ respectively. Thus,

$$P(E_1E_2E_3) = 2!(2 \cdot 96 + 2 \cdot 48 + 3 \cdot 64) / 8! = 1/42$$

Finally, there are 4! ways to order all four couples such that all couples are together. Hence, $P(E_1E_2E_3E_4) = 4!/8! = 1/1680$.

And so,

$$P(E_1 \cup E_2 \cup E_3 \cup E_4) = 4\cdot\frac{1}{4} - 6\cdot\frac{1}{14} + 4\cdot\frac{1}{42} -\frac{1}{1680} = \frac{1119}{1680}$$

Now obviously I did something wrong somewhere, but where?

 

[Skins]

You are definitely on the right track but it seems you fell into error in computing the very last term in your application of the inclusion-exclusion formula. Otherwise your work seems correct. In any event I'll run through my reasoning of this problem thus we may compare notes.

For P(E1) we have the case where one couple sits together. If we think of the couple which sits together as a single entity there are 7! ways they can be permuted among the remaining 6 persons. In other words I am looking at the couple that sits together as a single entity (as 1 person) permuted among 6 others, in other words a permutation of 7 "persons". In other words a permutation of the group

C P1 P2 P3 P4 P5 P6

where C represents the couple that sits together... and P1 ... P6 represent the remaining persons who do not sit together.

Now bear in mind for any couple that sits together there are 2! = 2 ways they can be permuted among each other. Thus for couple C consisting of a man/wife pair there are 2! permatations of the pair.
Therefore we have.

$4P(E1) = \frac{(4)(2)(7!)}{8!} = \frac{(4)(2)}{8} = \frac{8}{8} = 1$

which is what you got for the first term .

Now for the case where 2 couples sit together we reason the same way. Thinking of each couple that sits together as a single entity we have 6! permutations of the 2 couples and the remaining 4 persons. each of the couples that sit together can be permuted in 2! = 2 ways therefore

$6P(E1E2) = \frac{(6)(2^2)(6!)}{8!} = \frac{3}{7}$

We keep applying similar reasoning and get

$4P(E1E2E3) = \frac{(4)(2^3)(5!)}{8!} = \frac{2}{21}$

Thus far you are correct

Now for that last term
If all 4 couples sit together there are 2! = 2 permutations among each couple. There are 4! possible permutations of the couples among each other. i.e. a permuation of the 4 couples:

C1 C2 C3 C4

Furthermore each husband/wife pair can be permuted 2! ways and there are 4 couples. Therefore we have..

$P(E1E2E3E4) = \frac{(2^4)(4!)}{8!} = \frac{1}{105}$

Plugging into the inclusion-excusion formula we get

$P(E1 \cup E2 \cup E3 \cup E4) = 1 - \frac{3}{7} + \frac{2}{21} - \frac{1}{105} = \frac{23}{35}$

It was that last term that messed things up. Otherwise you seem to have reasoned the problem correctly.

Skins

 

[e(ho0n3]

I like your idea of considering the couple as a single "person". It definitely makes the problem easier than what I had made it out to be.

And yes, you're right that I messed up in calculating the probability that all four couples sit together. Thank you for pointing that out. I will mark the problem as solved.

Thanks again.

 

[Skins]

Yes, that does help to think of each couple that sits together as a single entity permuted among the remaining persons. As soon as I considered solving it that way the calculations became a lot simpler. As a matter of fact each of the terms $$4P(E1), 6P(E1E2), 4P(E1E2E3) and P(E1E2E3E4)$$ can be defined via the expression:

$C(4,n)\frac{2^n(8-n)!}{8!}$

where n is the number of married couples sitting together.

Thus for example:

$P(E1E2) = C(4,2)\frac{2^2(8-2)!}{8!}$

Anyway, glad to be of help in solving this problem. I wish there were forums like this around back in the days when i was learning this stuff.

Skins