Married Couples Problem

Also called the ménage problem. In how many ways can married couples be seated around a circular table in such a manner than there is always one man between two women and none of the men is next to his own wife? The solution (Ball and Coxeter 1987, p. 50) uses discordant permutations and was solved by Laisant, Moreau, and Taylor. The solution for can be given in terms of Laisant's recurrence formula

(1)

with and (Dörrie 1965, p. 33).

A closed form expression for in terms of a sum due to Touchard (1953) is

(2)

where is a binomial coefficient (Comtet 1974, p. 185; Vardi 1991, p. 123).

The first few values of for , 3, ... obtained from the recurrence and sum above are 0, 1, 2, 13, 80, 579, ... (OEIS A000179), which are sometimes called ménage numbers. The desired solution is then . The numbers can be considered a special case of a restricted rooks problem.

Equivalently, fix the women clockwise in alternate seats and let give the seats of the men. The reduced ménage number counts the permutations satisfying and modulo . If is the all-ones matrix, the identity matrix, and the cyclic permutation matrix, then

(3)

where is the permanent. More generally, for each permutation , let be its permutation matrix and define

(4)

The function is constant on each conjugacy class. Its Frobenius characteristic is the symmetric function

(5)

where is the Schur function indexed by the partition . Writing for the coefficient of , Renteln (2026) proves

(6)

where is the auxiliary sequence attributed to Moreau by Lucas (1891, p. 495; OEIS A000904). In particular, Moreau's numbers are the average of this family of permanents. They satisfy the recurrence relation

(7)

for , with and . When is an n, is conjugate to , so the reduced ménage number is

(8)

This gives the algebraic explanation for Moreau's sequence: its two-step differences are the reduced ménage numbers.