In a group of 2n people there are equally many men and…

In a group of $2n$ people there are equally many men and women. They take seats at a table at random. Determine the probability that no two people of the same gender sit next to each other.

Step 1: Only the gender pattern matters

Number the $2n$ seats. A random seating gives a random set of $n$ seats occupied by men; all $\binom{2n}{n}$ sets are equally likely (each corresponds to the same number $n!\,n!$ of seatings).

Step 2: Favourable patterns

No two people of the same gender are neighbours iff men and women alternate:

• seats in a row: M W M W … M W or W M W M … W M — $2$ patterns;
• round table ($2n$ seats in a circle, seat $2n$ next to seat $1$): men on all odd seats or on all even seats — again $2$ patterns (an even cycle alternates in exactly two ways).

Step 3: The answer

\[ \boxed{P=\frac{2}{\binom{2n}{n}}=\frac{2\,(n!)^2}{(2n)!}} \]

for both a row of seats and a round table.

Step 4: Round table, counting up to rotation

If we count circular arrangements up to rotation, there are $(2n-1)!$ of them. Fix one man's seat; the other $n-1$ men take the remaining $n-1$ seats of his parity in $(n-1)!$ ways and the women the other seats in $n!$ ways:

\[ P=\frac{(n-1)!\,n!}{(2n-1)!}=\frac{2n\,(n-1)!\,n!}{(2n)!}=\frac{2(n!)^2}{(2n)!}. \ \checkmark \]

Step 5: Values

For $n=1$ the two people are always of different genders, $P=1$. The probability falls quickly as the group grows.