the actual formula for circular permuatation is n!/n

The Gateway to Computer Science Excellence

0 votes

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?

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?

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!

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

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

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

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

+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

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.

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

52,345 questions

60,503 answers

201,881 comments

95,331 users