sitting n married couples on a round table

lizzyb

Question: A total of 2n people, consisting of n married couples, are randomly seated (all possible orderings being equally likely) at a round table. Let C_i denote the event that couple i are seated next to each other, i = 1, 2, ... n.

(a) Find P(C_i).

There are two different ways to seat C_i together on a round table and the possible orderings of the rest of the couples is (2n - 2)!, hence we have:

P(C_i) = (2 * (2n - 2)!)/(2n - 1)!) = 2/(2n - 1)

The the (2n - 1)! being the total number of orderings (C_i included) on a round table. The book gives an answer of 2/(2n + 1).

What am I doing wrong?

(b) For j <> i, find P(C_j | C_i)

Instead of using the P(C_j | C_i) = P(C_j C_i) / P(C_i) formula, we may cut to the chase and say that since a couple has already been selected, we can view the round table as a straight line. So the number of ways to arrange C_j are:

i) 2 choices on which of the couple to sit
ii) Pick a place among (2n - 3) seats
iii) Place the other couple on the other side (1 choice)

2 (2n - 3)

So P(C_j | C_i) = ( 2 (2n - 3) (2n - 4)! )/ (2n - 2)! = 2 / (2n - 2)

Which is in the back of the book

(c) When n is large, approximate the probability that there are no married couples who are seated next to each other.

I imagine we're supposed to use the Poisson distribution?

D H

In short, you are ignoring that the table is round, and this changes things. There is a very easy way to solve this problem: What is the probability that the couple is not seated next to one another?

lizzyb

There are 2n places for the first member of the couple, then 2n-2 places for the other member.

So P(E_i) = ( (2n)(2n - 2)(2n-2)! )/(2n-1)!??

D H

You did not answer my question. I asked you to compute the probability that the couple are not seated next to one another. Call this probability q. The probability that the couple are seated next to one another is p=1-q.

lizzyb

That's what I meant by ( (2n)(2n - 2)(2n-2)! )/(2n-1) but that's probably not right.

Since its a round table, we can say that the location of the first person placed upon it doesn't matter, but for the other member of that couple, there are 2n-2 places to put him or her (since there are two places on either side of the first seat where his/her partner is). After these two have been placed, there are still the other people, of which there are (2n-4)! possible seating arrangements. This all goes over (2n-1)! since that is the total number of possible permutations of 2n people on a round table:

q = (2n - 2)(2n - 4)!/(2n - 1)! = 1 / (2n - 1)(2n - 3)

does that look right to you?

konthelion

For part (a) you did it correctly! The book is wrong :)

There are [tex](2n-1)![/tex] ways to arrange 2n people. Since the couple with index i are sitting together, you can think of them as one person thus you get [tex](2n-2)![/tex]. But, there are 2 ways to arrange couple with index i.

Thus

[tex]\boxed{P(C_{i})=\frac{2(2n-2)!}{(2n-1)!}=\frac{2}{2n-1}}[/tex]

(b) Well, you can further simplify it into [tex]\frac{1}{n-1}[/tex]

(c) Yes, you use the Poisson r.v. distribution with parameter [tex]\lambda = pn[/tex]. Now what is p? Then just find the probability that no couple are sitting together i.e. [tex]\boxed{P[X=0] = e^{-\lambda}}[/tex] by definition of Poisson

D H

I took a second look, sorry.
You are doing nothing wrong. The book is what is wrong. The answer is 2/(2n-1) (n>1).

Consider one member of the couple in question. If the couple is not seated adjacently, both seats next to this one member of the couple must be filled someone other than the other member of the couple. These are the only two seats one need be concerned with, and the probability neither is the other member of the couple is (2n-2)/(2n-1)*(2n-3)/(2n-2)=(2n-3)/(2n-1)=1-2/(2n-1). The probability the couple *are* seated adjacently is thus 2/(2n-1).

As a sanity check, look at the case n=2. The only way a couple is not seated adjacently at a table of four is when they are seated across from one another. There are 4*2 such seatings out of a total of 24, so the probability they are seated adjacently is 16/24=2/3.

lizzyb

Great! Thank you for verifying part a as well as the other way of understanding it as well.

As for part (c), I suppose I'm to guess a decent value of p based on the answers of (a) and (b)?

(a) P(C_i) = 2/(2n - 1)
(b) P(C_j | C_i) = 1/(n-1) (i <> j)

And this p should be a general guesstimate of the probability that a couple sits together? Both (a) and (b) are similar to 1/n ... that gives the right answer in the back of the book but I can't say I fully understand why it works.

Thanks for your help!

[Added later]
No, 1/n makes sense but is that the right question to ask myself in answering "what value of p" - that is, "what is the general probability of a single couple sitting together"?

konthelion

Yes, which you have already found namely [tex]P(C_{i}) [/tex]