You have a dinner-party, with a big, round table in the center of the room.

probability/menages New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

You have a dinner-party, with a big, round table in the center of the
room.  N married couples have been invited to the party, and the seats
round the table are alternately "man" and "woman" seats.  Now, if the
husbands are randomly assigned the "man" seats, and the wives the
"woman" ones, what is the probability that no married couple at all
will sit next to each other?

-- Samuel Gustaf Siren <samuel@front.se>

Show solution

This is the famous "probleme des menages."  The answer is the following
number divided by n!

  n
  -      k  2n   / 2n-k \
  >  (-1)  ---- |        | (n-k)!
  -        2n-k  \  k   /
 k=0

The limiting probability is 1/e^2.  See, for instance, Kaplansky,
Solution of the "probleme des menages," Bull. Amer. Math. Soc. 49
(1943), 784-785, or Stanley, _Enumerative_Combinatorics_, vol. 1,
sec. 2.3, Wadsworth & Brooks/Cole, 1986.

-- Tim Chow <tycchow@math.mit.edu>