The Gateway to Computer Science Excellence
0 votes
170 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?
in Probability by Active (5.1k points)
edited by | 170 views
+1
we dont fix one item

the actual formula for circular permuatation is n!/n
0
I mean , from where the formula comes?
0

@Satbir you're right actually
https://math.stackexchange.com/questions/2387149/explanation-circular-permutation
learnt a new thing


so in this question we're not fixing a person's position?
we're finding no. of distinct circular arrangements
right?

+1
suppose we have to arrange 3 people ABC in circular table

ABC , CAB , BCA are counted as one.because these arrangements are clockwise rotation of one another

BAC,CBA,ACB are counted as one because the arrangement are clockwise rotation of one another

So in circular permutation they will look same and hence are counted as one.

So total ways = 2

i.e. N!/N = (N-1)! = 3!/3 = 2!
0

@aditi19

In this after making the couple a unit after that we are calculating the circular permutation of (remaining people+1 unit)

0
yes.

check then when you r choosing $3$ couple , then their sitting arrangement will be $3!\times 2!$

right ?

when u r doing $2^{3}=8$ then only $8$ arrangement possible, but actually should be more than that.

right??
+1

circular permutation $\leq$ normal permutation always.

choosing 3 couples = $^{10}C_3$

now couple 1 -> 1 unit, couple 2 -> 1 unit, couple 3 -> 1 unit.

so total 14+1+1+1 = 17 people

so circular permutation is $16!$

now couple 1 can sit as $husband_1wife_1$ or $wife_1husband_1$ = $2$ ways

now couple 2 can sit as $husband_2wife_2$ or $wife_2husband_2$ = $2$ ways

now couple 3 can sit as $husband_3wife_3$ or $wife_3husband_3$ = $2$ ways

So total ways = $^{10}C_3$*$16!$*2*2*2

the extra cases which you are saying @srestha are already included when we are calculating circular permutation

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.

0

@Satbir

I've one more doubt

circular permutation=$\frac{n!}{n}$

and necklace permutation=$\frac{n!}{2n}$

could you give some insight into necklace permutation formula?

+1

In case of circular permutation direction matters i.e.{ c1,c2,c3} and {c3,c2,c1} are 2 arrangements one in clockwise and other in anticlockwise.

But in case of necklace permutation direction doesn't matter  i.e.{ c1,c2,c3} and {c3,c2,c1} is 1 arrangements because we can take a necklace ,flip it and again wear it. You can't tell the difference whether we have flipped the necklace or not. (ulta side = sidha side in a necklace)

example:

 

So cases reduces to half that's why we divide by 2.

 

0
got it

thank u👍

1 Answer

+4 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.
 

by Boss (21.5k points)
selected 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
50,648 questions
56,430 answers
195,213 comments
99,927 users