3
$\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?

$\endgroup$
5
  • 1
    $\begingroup$ Possible duplicate of math.stackexchange.com/questions/68541/… $\endgroup$
    – Daniel R
    Commented Aug 8, 2013 at 19:00
  • $\begingroup$ Different question, though answer there can be used as a component. $\endgroup$ Commented Aug 8, 2013 at 19:19
  • $\begingroup$ @AndréNicolas: Hmm, what's different about them? $\endgroup$
    – Daniel R
    Commented Aug 8, 2013 at 19:44
  • 1
    $\begingroup$ You are right, I was mistaken. $\endgroup$ Commented Aug 8, 2013 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
    Commented Aug 8, 2013 at 20:23

3 Answers 3

4
$\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 seat #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 in 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

$\endgroup$
1
  • 1
    $\begingroup$ Great answer! And the easiest one to understand as well! Well explained! $\endgroup$
    – Ankit Seth
    Commented Jul 23, 2021 at 11:21
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.

$\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$).

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .