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. (Ménage is the French word for "household", referring here to a male-female couple.) This problem was formulated in 1891 by Édouard Lucas and independently, a few years earlier, by Peter Guthrie Tait in connection with knot theory. For a number of couples equal to 3, 4, 5, ... the number of seating arrangements is
12, 96, 3120, 115200, 5836320, 382072320, 31488549120, ... (sequence A059375 in the OEIS). Mathematicians have developed formulas and recurrence equations for computing these numbers and related sequences of numbers. Along with their applications to etiquette and knot theory, these numbers also have a graph theoretic interpretation: they count the numbers of matchings and Hamiltonian cycles in certain families of graphs.
Touchard's formula Let Mn denote the number of seating arrangements for n couples. Touchard (1934) derived the formula
M n = 2 ⋅ n ! ∑ k = 0 n ( − 1 ) k 2 n 2 n − k ( 2 n − k k ) ( n − k ) ! . {\displaystyle M_{n}=2\cdot n!\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!.}
Much subsequent work has gone into alternative proofs for this formula and into various generalized versions of the problem. A different umbral formula for Mn involving Chebyshev polynomials of first kind was given by Wyman & Moser (1958).
Ménage numbers and ladies-first solutions There are 2×n! ways of seating the women: there are two sets of seats that can be arranged for the women, and there are n! ways of seating them at a particular set of seats. For each seating arrangement for the women, there are
A n = ∑ k = 0 n ( − 1 ) k 2 n 2 n − k ( 2 n − k k ) ( n − k ) ! {\displaystyle A_{n}=\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!}
ways of seating the men; this formula simply omits the 2×n! factor from Touchard's formula. The resulting smaller numbers (again, starting from n = 3),
1, 2, 13, 80, 579, 4738, 43387, 439792, ... (sequence A000179 in the OEIS) are called the ménage numbers. The factor 2 n 2 n − k ( 2 n − k k ) {\displaystyle {\frac {2n}{2n-k}}{2n-k \choose k}} is the number of ways of forming k non-overlapping pairs of adjacent seats or, equivalently, the number of matchings of k edges in a cycle graph of 2n vertices. 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. Until the work of Bogart & Doyle (1986), solutions to the ménage problem took the form of first finding all seating arrangements for the women and then counting, for each of these partial seating arrangements, the number of ways of completing it by seating the men away from their partners. 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. 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). The ménage numbers satisfy the recurrence relation
A n = n A n − 1 + n n − 2 A n − 2 + 4 ( − 1 ) n − 1 n − 2 {\displaystyle A_{n}=nA_{n-1}+{\frac {n}{n-2}}A_{n-2}+{\frac {4(-1)^{n-1}}{n-2}}}
and the simpler four-term recurrence
… excerpt ends here. Continue reading the full article.
