Ménage problem

In combinatorial mathematics, the ménage problem or problème des ménages asks for the number of different ways in which it is possible to seat a set of male-female couples at a round dining table so that men and women alternate and nobody sits next to his or her partner.

This problem was formulated in 1891 by Édouard Lucas and independently, a few years earlier, by Peter Guthrie Tait in connection with knot theory.

A different umbral formula for Mn involving Chebyshev polynomials of first kind was given by Wyman & Moser (1958).

The expression for An is the immediate result of applying the principle of inclusion–exclusion to arrangements in which the people seated at the endpoints of each edge of a matching are required to be a couple.

Bogart and Doyle argued that Touchard's formula may be derived directly by considering all seating arrangements at once rather than by factoring out the participation of the women.

[2] However, Kirousis & Kontogeorgiou (2018) found the even more straightforward ladies-first solution described above by making use of a few of Bogart and Doyle's ideas (although they took care to recast the argument in non-gendered language).

Solutions to the ménage problem may be interpreted in graph-theoretic terms, as directed Hamiltonian cycles in crown graphs.

Any valid seating arrangement can be described by the sequence of people in order around the table, which forms a Hamiltonian cycle in the graph.

In a reduced diagram, the two labels at a crossing cannot be consecutive, so the set of pairs of labels at each crossing, used in Dowker notation to represent the knot, can be interpreted as a perfect matching in a graph that has a vertex for every number in the range from 1 to 2n and an edge between every pair of numbers that has different parity and are non-consecutive modulo 2n.

A table with ten place settings. There are 3120 different ways in which five male-female couples can sit at this table such that men and women alternate and nobody sits next to their partner.
Crown graphs with six, eight, and ten vertices. The outer cycle of each graph forms a Hamiltonian cycle; the eight and ten vertex graphs also have other Hamiltonian cycles.