Circular table $2n$ men $n$ women, probability that no two women sit next to each other

combinatoricsprobability

There is circular table with $3n$ chairs, there are $2n$ men and $n$ women. What is the probability of event such that no two women sit next to each other, in other words every woman has to have man in her left and right.

My solution:

  1. Sit women. They will sit next to each other for now, in next step we put men's between them $n!$
  2. Choose $n$ men's and sit them next to women. ${2n \choose n}n!$
  3. Choose chairs for left men's, they have to sit next to already sitting men's since we
    already chose men's that will sit next to women's. $n(n+1)…(2n-1)$ The product is
    increasing becuase if we sit first man then there is one more place for another and so on
  4. Sit $n$ left men's. $n!$

So the probability is $\frac{n!{2n \choose n}n!n(n+1)…(2n-1)n!}{(3n)!}$

Solution of someone else:

Since its circle there are $\frac{(3n)!}{3n}(3n-1)!$ all possible sittings because sittings which differ by rotations are the same.

  1. Sit first woman somewhere.
    Now chairs are distinguishable.
  2. Sit $n-1$ woman to $3n-3$ chairs (3n-1-2, since 1 woman is already sitting and her neighbours have to be man) in such a way they don't sit next to each other. It is equivalent to count functions $f$ from {$1,…,n-1$} to {$1,…,3n-3$} such that $f(i)+2 \leq f(i+1)$ and then multiply by $(n-1)!$. To count these functions it is equivalent to counting increasing functions from {$1,…,n-1$} to {$1,…,2n-1$} $(g(i)=f(i)-i+1)$ is bijection.
    So there are ${2n-1 \choose n-1}(n-1)!$ ways to to it.
  3. Sit men's. $(2n)!$

So the probability is $\frac{(2n)!(n-1)!{2n-1 \choose n-1}}{(3n-1)!}$

I have couple questions.

  1. Second solution consider sittings which differ by rotations the same. Is it standard way to do this type of problems?
  2. Is my solution correct if I don't consider sittings which differ by rotations the same? If it is still not correct then why? I think it is not correct since for $n=1$ probability is not $1$, but where is mistake in my solution?
  3. I think second solution is correct, is it?
  4. Assuming one calculate properly in two ways (considering sitting which differ by rotations different and same) are probabilities the same?

Best Answer

The usual convention is that arrangements which differ by a rotation are considered to be equivalent. That said, labeling the seats does not affect the probability that no two women sit next to each other.

I will show you a different approach, then compare answers. In what follows, I will treat the seats as unlabeled so that only the relative order of the people matters.

Suppose Alvin is one of the men. Seat Alvin. We will use him as our reference point. Relative to Alvin, there are $(3n - 1)!$ ways to seat the rest of the people as we proceed clockwise around the table.

To count the favorable cases, we begin as above. Seat Alvin. Relative to Alvin, the remaining men can be seated in $(2n - 1)!$ ways as we proceed clockwise around the table. Doing so creates $2n$ spaces in which to seat the women, one to the left of each of the men. To separate the women, we choose $n$ of these $2n$ spaces in which to place a woman, which can be done in $\binom{2n}{n}$ ways. The $n$ women can be arranged in the selected spaces in $n!$ ways as we proceed clockwise around the table from Alvin. Hence, the probability that no two of the women are adjacent is $$\frac{(2n - 1)!\binom{2n}{n}n!}{(3n - 1)!}$$

Let's compare this with the second solution. The denominators are the same, so it suffices to check that the numerators are equal. \begin{align*} (2n)!(n - 1)!\binom{2n - 1}{n - 1} & = (2n)!(n - 1)! \cdot \frac{(2n - 1)!}{(n - 1)!n!}\\ & = \frac{(2n)!n(n - 1)!(2n - 1)!}{n(n - 1)!n!}\\ & = \frac{(2n)!n!(2n - 1)!}{n!n!}\\ & = \frac{(2n)!}{n!n!} \cdot n!(2n - 1)!\\ & = \binom{2n}{n}n!(2n - 1)! \end{align*} so the second solution is indeed correct.

If the seats were labeled, we would just multiply the numerator and the denominator by the $3n$ ways we could seat Alvin. Therefore, labeling the seats does not change the probability.

Your attempt is wrong since you first sat $n$ men next to the women, then sat $n$ men next to those men, then sat $n$ more men. However, there are only $2n$ men. There is also a more subtle reason your answer is wrong. Say Alvin is sitting to the immediate left of Barbara. If you then seat Charles to the immediate left of Alvin and David to the immediate left of Charles, you would get the same arrangement by seating David to the immediate left of Alvin and then sitting Charles to the immediate left of Alvin.

Related Question