Sheldon Ross Example-5n

Question

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?

Comments

@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?

---

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.

 

---

got it

thank u👍

Answer 1

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

Comments

@Satbir
u actually calculated it :P