1
$\begingroup$

I have a probability question that reads:

Question:

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

My attempt:

Total outcomes = 8!
Outcomes that all of them sit with their wife: 4!*(4*2!)
Outcomes that one of them sit with their wife: (2!*4)(6!)-(2!*4)(3!*(3*2!)[subtract the ways that remaining couples are together]
Outcomes that two of them sit with their wife: (2!*4C2)(4!)-(2!*4C2)(2!*(2*2!)
Outcomes that three of them sit with their wife: (2!*4C3)(2!)-(2!*4C3)(1!*(2*2!)
Hence no husband sit with wife is 1 -(Outcomes that all of them sit with their wife+ Outcomes that one of them sit with their wife + Outcomes that two of them sit with their wife + Outcomes that three of them sit with their wife)/8!

Am i right? Any easier way?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Possible duplicate of math.stackexchange.com/questions/68541/… $\endgroup$ – Daniel R Aug 8 '13 at 19:00
  • $\begingroup$ Different question, though answer there can be used as a component. $\endgroup$ – André Nicolas Aug 8 '13 at 19:19
  • $\begingroup$ @AndréNicolas: Hmm, what's different about them? $\endgroup$ – Daniel R Aug 8 '13 at 19:44
  • 1
    $\begingroup$ You are right, I was mistaken. $\endgroup$ – André Nicolas Aug 8 '13 at 19:53
  • 1
    $\begingroup$ You can always try ruby: [1,-1,2,-2,4,-4,8,-8].permutation.map{|p| [p[0..-2].zip(p[1..-1]).map{|t| t.inject(:+)}.inject(:*).abs, 1].min}.inject(:+), or try haskell: sum $ map (\p -> min 1 $ abs $ product $ map (uncurry (+)) $ zip p $ tail p) $ permutations [1,-1,2,-2,4,-4,8,-8] $\ddot\smile$ $\endgroup$ – dtldarek Aug 8 '13 at 20:23
3
$\begingroup$

I cannot think of anything pleasant. A natural approach is through Inclusion/Exclusion.

There are $8!$ arrangements. If we can count the bad arrangements, in which at least one couple is together, then the rest is easy.

Call the couples A, B, C, D and let $X$ be the wife in couple X, and $x$ the husband. It is not hard to count the arrangements in which $a$ is next to $A$, and similarly for the other $3$ couples.

If we add these $4$ numbers, we will have double-counted, in particular, the arrangements in which couple A and couple B are both together. So we need to subtract $\binom{4}{2}$ times the number of arrangements in which couple A and couple B are together.

But we have subtracted too much. So we add back $\binom{4}{1}$ times the number of arrangements in which couples A, B, and C are together.

But we have added back too much, so we must subtract the number of ways for all the couples to be next to each other.

Instead of counting, we can apply Inclusion/Exclusion directly to probabilities. It is marginally easier.

Improve this answer
$\endgroup$
2
$\begingroup$

With $n$ couples, the probability of no couple sitting together is $$\displaystyle\sum_{i=0}^n (-2)^i {n \choose i}\frac{(2n-i)!}{(2n)!}.$$

This comes from using inclusion-exclusion, and (as I said in the previous question) treating a couple sitting together as a single individual (hence the $(2n-1)!$), though one of each pair can be on the left or right (hence the $2^i$).

Improve this answer
$\endgroup$
  • $\begingroup$ I wonder if this is one of many cases which converge to $e^{-1} \approx 0.367879$ as $n$ increases? $\endgroup$ – Henry Aug 11 '13 at 20:37
  • $\begingroup$ It does - see math.stackexchange.com/questions/465318/… $\endgroup$ – Henry Aug 12 '13 at 23:20
2
$\begingroup$

It's 8! minus all the unwanted seating arrangements:

So we have to calculate the number of unwanted seating arrangements this way:

Let A = the unwanted case that couple 1 sits together. Let B = the unwanted case that couple 2 sits together. Let C = the unwanted case that couple 3 sits together. Let D = the unwanted case that couple 4 sits together.

So we want N(A or B or C or D)

The "sieve" formula for the answer (sometimes called the "inclusion and exclusion" formula is:

N(A or B or C or D) = N(A) + N(B) + N(C) + N(D) - N(A&B) - N(A&C) - N(A&D) - N(B&C) - N(B&D) - N(C&D) + N(A&B&C) + N(A&B&D) + N(A&C&D) + N(B&C&D) - N(A&B&C&D)

It's easy to see that:

N(A) = N(B) = N(C) = N(D) N(A&B) = N(A&C) = N(A&D) = N(B&C) = N(B&D) = N(C&D) N(A&B&C) = N(A&B&D) = N(A&C&D) = N(B&C&D)

So the "sieve" formula becomes

N(A or B or C or D) = 4N(A) - 6N(A*B) + 4N(A&B&C) - N(A&B&C&D)

We calculate N(A)

We will use (x,y) to mean that a couple sits in seats #x and #y

Choose couple 1's seats 7 ways: (1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8) Choose the way they can sit 2! ways: (husband,wife) or (wife,husband) Seat the other 6 people 6! ways.

That's 7×2!×6! = 10080

N(A&B) = 10080

We calculate N(A&B)

Couples 1 and 2 can use 4 seats in these 15 ways:

{(1,2),(3,4)}, {(1,2),(4,5)}, {(1,2),(5,6)}, {(1,2),(6,7)}, {(1,2),(7,8)}, {(2,3),(4,5)}, {(2,3),(5,6)}, {(2,3),(6,7)}, {(2,3),(7,8)}, {(3,4),(5,6)}, {(3,4),(6,7)}, {(3,4),(7,8)}, {(4,5),(6,7)}, {(4,5),(7,8)}, {(5,6),(7,8)}

Choose whether couple 1 is left of couple 2 or vice-versa in 2! ways: Choose the way couple 1 can sit 2! ways: (husband,wife) or (wife,husband) Choose the way couple 2 can sit 2! ways: (husband,wife) or (wife,husband) Seat the remaining 4 people 4! ways.

That's 15×2!×2!×2!×4! = 2880 ways.

N(A&B) = 2880

We calculate N(A&B&C)

Couples 1, 2 and 3 can use 6 seats in these 10 ways:

{(1,2),(3,4),(5,6)}, {(1,2),(3,4),(6,7)}, {(1,2),(3,4),(7,8)}, {(1,2),(4,5),(6,7)}, {(1,2),(4,5),(7,8)}, {(1,2),(5,6),(7,8)}, {(2,3),(4,5),(6,7)}, {(2,3),(4,5),(7,8)}, {(2,3),(5,6),(7,8)}, {(3,4),(5,6),(7,8)}

We can choose the order of the 3 couples is 3! or 6 ways. Choose the way couple 1 can sit 2! ways: (husband,wife) or (wife,husband) Choose the way couple 2 can sit 2! ways: (husband,wife) or (wife,husband) Choose the way couple 3 can sit 2! ways: (husband,wife) or (wife,husband) Seat the remaining 2 people 2! ways.

That's 10×3!×2!×2!×2!×2! = 960 ways.

N(A&B&C) = 960

We calculate N(A&B&C&D) (They use all 8 seats) Choose the order of the 4 couples 4! = 24 ways Choose the way couple 1 can sit 2! ways: (husband,wife) or (wife,husband) Choose the way couple 2 can sit 2! ways: (husband,wife) or (wife,husband) Choose the way couple 3 can sit 2! ways: (husband,wife) or (wife,husband) Choose the way couple 4 can sit 2! ways: (husband,wife) or (wife,husband)

That's 4!×2!×2!×2!×2! = 384

Substitute in "sieve" formula to get the number of unwanted seating arrangements:

N(A or B or C or D) = 4N(A) - 6N(A&B) + 4N(A&B&C) - N(A&B&C&D)

N(A or B or C or D) = 4(10080) - 6(2880) + 4(960) - 384 = 26496

Subtract from 8!:

8! - 26496 = 40320 - 26496 = 13824.

Answer: 13824

Edwin McCravy

Improve this answer
$\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.