The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
144 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 (3.9k points)
edited by | 144 views
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 (17.2k 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
49,807 questions
54,730 answers
189,326 comments
79,942 users