The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
79 views
Compute the probability that if 10 married couples are seated at random at a round table, then no wife sits next to her husband

1 wife sits next to her husband. pick one of the 10 couples=$\binom{10}{1}$. These couples can interchange their position such that they sit next to each other in $2^1$ ways
now let the couple form a unit. so there are 18+1=19 people who have to be arranged in circular permutation. this can be done in (19-1)! ways

so for one couple → $\binom{10}{1}*18!*2^1$

for 2 couples → $\binom{10}{2}*17!*2^2$ [here the two couples can interchange their position so 2*2 permutations can be done]
here the two couples forms 2 units. so total 2+16=18 people have to be arranged in circular permutation. this can be done in 17! ways
3 couples → $\binom{10}{3}*16!*2^3$
4 couples → $\binom{10}{4}*15!*2^4$
5 couples → $\binom{10}{5}*14!*2^5$
6 couples → $\binom{10}{6}*13!*2^6$
7 couples → $\binom{10}{7}*12!*2^7$
8 couples → $\binom{10}{8}*11!*2^8$
9 couples → $\binom{10}{9}*10!*2^9$
10 couples → $\binom{10}{10}*9!*2^{10}$

Atleast one couple sits together
=$\binom{10}{1}*18!*2^1$ – $\binom{10}{2}*17!*2^2$ + $\binom{10}{3}*16!*2^3$ – $\binom{10}{4}*15!*2^4$ + $\binom{10}{5}*14!*2^5$ – $\binom{10}{6}*13!*2^6$ + $\binom{10}{7}*12!*2^7$ – $\binom{10}{8}*11!*2^8$  + $\binom{10}{9}*10!*2^9$ – $\binom{10}{10}*9!*2^{10}$
=N

probability that atleast one couple sits together=$\frac{N}{19!}$

so probability that no couple sits together=$1-\frac{N}{19!}$

is this correct?
asked ago in Probability by Active (3.7k points)
edited ago by | 79 views
0

@Satbir

Can u tell me how $8$ is coming?

$8$ means either one couple selected, or $2$ couple of $3$ couple, w.r.t. their position. But is it the case is not same here.

 

now couple 1 can sit as husband1wife1 or wife1husband1 = 2 ways

now couple 2 can sit as husband2wife2 or wife2husband2 = 2 ways

now couple 3 can sit as husband3wife3 or wife3husband3 = 2 ways

No, these case not included inside $8.$ Chk once more

0

8 means either one couple selected, or 2 couple of 3 couple, w.r.t. their position.

We don't need to do this because we already selected 3 couples  using $^{10}C_3$. then we make them a unit

$8$ is $2*2*2$.= (inside one unit how many ways a couple1 can be arranged)*(inside one unit how many ways a couple2 can be arranged)*(inside one unit how many ways a couple3 can be arranged)

when we make couple 1 as a unit then inside that unit we can arrange husband wife in 2 ways

when we make couple 2 as a unit then inside that unit we can arrange husband wife in 2 ways

when we make couple 3 as a unit then inside that unit we can arrange husband wife in 2 ways

we are making them unit because we want that there should be three couples where husband wifes sits togather.

Its same like in string ABUC all vowels should be togather.

why do we need to do like 1 couple selected , 2 couple selected wrt to their position ?

The position part of couples wrt each other is handled when we are calculating circular permuation because in circular permutation we are adding each couple as a unit like 14 +1+1+1 . these '1' is for each of the 3 couples.

 

0

See how can we arrange $8$ possibility

like if 3 couples are {AB},{CD},{EF}

Now, these 3 couple can arrange $8$ ways??

{AB} {CD} {EF}
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1


Now how these $8$ ways formed?

either we select none of couple  (or) Select {AB} alone, or select {AB},{CD} together or all three,........

but we never taking AB and BA as two possibility.

right??

So, ur logic according to $8$ or $3$ couples is not correct.

 

 

0

See my answer , For calculating  C3

out of the 8 cases which you provided above ....out of those 8 cases we are going with the last case always i.e. AB,CD,EF all 3 are selected always using $^{10}C_3$. So there is no point in considering all those 8 cases.


After selecting the 3 couples we are not arranging couples, we are arranging husband wife inside each couple.

Suppose we have a case as XYZ  where X is couple1 Y is couple 2 and Z is couple 3 then

(AB or BA) *(CD or DC) *(EF or FE) 2*2*2 =8 ways i.e. we have 8 ways or arranging 6 people or 3 couples for the case XYZ.

This 8 is used in the answer


Arrangement of couples is covered under circular permuation ways i.e. under 16! ways.

i.e. like XYZ or YZX or YXZ ....6 cases this thing is covered inside 16! ways where X is couple1 Y is couple 2 and Z is couple 3


 

0
Then why r u multiplying 2 ,2 and 2?? why r u not adding them??
0
just take a small example, of 3 couple or 4 couples, and tell me what those $8$ cases are.
+2

(AB or BA) *(CD or DC) *(EF or FE)= 2*2*2 =8 ways

for $XYZ$

where here $X = AB, X'=BA, Y= CD, Y'=DC, Z = EF , Z'= FE$

i am not changing ordering between couples i.e. not doing $YXZ$ (this in included in the 16! cases)

$XYZ$

$XYZ'$

$XY'Z$

$XY'Z'$

$X'YZ$

$X'YZ'$

$X'Y'Z$

$X'Y'Z'$

 

the possible ordering is 2*2*2 not 2+2+2 because in each arrangement one case is depending on other i.e. X depends on Y and Z and vice versa (multiplication law) for generating a new arrangement.

 

 

 

0

@srestha

@aditi19

Can you please message me a link to download pdf of sheldon ross book.

+1

yes right. I misinterpreted 0 and 1.

@Satbir

I think u can get the book online.

1 Answer

+2 votes
Best answer

$P(no\ husband\ wife\ sits\ together) $

$= 1- P(atleast\ 1\ couple\ sits\ together)$

$= 1 - P(1\ couple\ sits\ together\ U\ 2\ couple\ sits\ together\ U\ ....U\ 10\ couples\ sits\ together)$


                                     

Let $Husband_1\ and\ Wife_1$ sit together. They can sit together in $2$ ways i.e. $Husband_1 Wife_1$ or $Wife_1Husband_1$

Let $Husband_1\ and\ Wife_1$ be $X$ i.e. they form a unit.

so there are $18+1(X)=19$ people who have to be arranged in circular permutation which can be done in $(19-1)!$ ways.

So couple $1$ can sit together in $18! *2$ ways

And we have $10$ such couples.

so $C_1$ = $1$ couple sit together  → $10*18!*2^1$ ways = $128,0 47,47 4,114 ,560,000$ ways



$C_2$ = $2$ couples can sit togeher → $\binom{10}{2}*17!*2^2$ ways = $64,023,737,057,280,000$ ways

Here the $2$ couples can interchange their position so $2*2$ permutations can be done
Here the $2$ couples forms $2$ units.i.e.

Let $Husband_1\ and\ Wife_1$ be $X$ i.e. they form a unit.

Let $Husband_2\ and\ Wife_2$ be $Y$ i.e. they form a unit.

so total $1(X)+1(Y)+16=18$ people have to be arranged in circular permutation which can be done in $17!$ ways.


Similarly,


$C_3$ =$3$ couples can sit together → $\binom{10}{3}*16!*2^3$ ways = $20,085,878,292,480,000$ ways
$C_4$ =$4$ couples can sit together → $\binom{10}{4}*15!*2^4$ ways = $4,393,785,876,480,000$ ways
$C_5$ =$5$ couples can sit together → $\binom{10}{5}*14!*2^5$ ways = $703,0 05,74 0,236,800$ ways
$C_6$ =$6$ couples can sit together → $\binom{10}{6}*13!*2^6$ ways = $83,691,159,552,000$ ways
$C_7$ =$7$ couples can sit together → $\binom{10}{7}*12!*2^7$ ways = $7,357,464,576,000$ ways
$C_8$ =$8$ couples can sit together → $\binom{10}{8}*11!*2^8$ ways = $459,841,536,000$ ways
$C_9$ =$9$ couples can sit together → $\binom{10}{9}*10!*2^9$ ways = $18,579,456,000$ ways
$C_{10}$ =$10$ couples can sit together → $\binom{10}{10}*9!*2^{10}$ ways = $371,589,120$ ways


According to the $Inclusion-exclusion\ principle$,

$Number\ of\ ways\ atleast\ 1\ couple\ sits\ together$

$=(1\ couple\ sits\ together)\ U\ (2\ couple\ sits\ together)\ U\ ....U\ (10\ couples\ sits\ together)$

$=C_1 - C_2+C_3-C_4+C_5-C_6+C_7-C_8+C_9-C_{10}$ 

$=(C_1 +C_3+C_5+C_7+C_9)-(C_2+C_4+C_6+C_8+C_{10})$ 

$= 148,843,734,191,308,800 - 68,501,674,306,437,120$

$=80,342,059,884,871,680$



$P(atleast\ 1\ couple\ sits\ together)$ = $\frac{80,342,059,884,871,680}{19!}$ = $\frac{80,342,059,884,871,680}{121,645,100,408,832,000}$ = $ 0.66046276928$

$P(no\ couple\ sits\ together) $ = $1-0.66046276928$=$0.33953723072$  Answer.
 

answered ago by Boss (12.8k points)
selected ago by
+1

@Satbir
u actually calculated it :P

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,081 answers
187,200 comments
70,990 users