The ménage problem

The ménage problem (problème des ménages) asks for the number of ways of seating man-woman couples at a circular table, with men and women alternating, so that no one sits next to his or her partner. This famous problem was initially posed by Lucas [8] in 1891, though an equivalent problem had been raised earlier by Tait [12] in connection with his work on knot theory (see Kaplansky and Riordan [6]). This problem has been discussed by numerous authors (see the references listed in [6]), and many solutions have been found. Most of these solutions tell how to compute using recurrence relations or generating functions, as opposed to giving an explicit formula. The first explicit formula for , was published by Touchard [13] in 1934, though he did not give a proof. Finally, in 1943, Kaplansky [5] gave a proof of Touchard's formula. Kaplansky's derivation was simple but not quite straight-forward, and the problem is still generally regarded to be tricky.

We will present a completely straight-forward derivation of Touchard's formula. Like Kaplansky's, our solution is based on the principle of inclusion and exclusion (see Ryser [11] and Riordan [9]). What distinguishes our approach is that we do not seat the ladies (or gentlemen) first.