The married couples problem, also called the ménage problem, asks how many ways
married couples can be seated around a circular table with men and women alternating
and no person next to their spouse. The solution (Ball and Coxeter 1987, p. 50)
uses discordant permutations and was solved
by Laisant, Moreau, and Taylor. The reduced numbers satisfy Laisant's
recurrence formula
(1)
for ,
with
and
(Dörrie 1965, p. 33).
A closed form expression for in terms of a sum due to Touchard (1934) is
The first few values of for , 3, ... obtained from the recurrence
relation and sum above are 0, 1, 2, 13, 80, 579, ... (OEIS A000179),
which are sometimes called ménage numbers. For labeled seats, the total is . If seatings differing only by a rotation
are identified, the count is . 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
for ,
with
and .
For ,
when
is an n-cycle, 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.
A related problem forbids offsets and rather than 0 and 1. For , let count permutations
of
satisfying
for every .
With ,
the values for ,
1, 2, ... are 1, 0, 1, 1, 4, 13, 82, 579, 4740, ... (OEIS A354152).
André (2026) proved that for odd and for even , settling the latter relation, which had been conjectured.
André (2026) also gave polynomial-time ranking and unranking algorithms when
any two distinct offsets modulo are forbidden.
Abramson, M. and Moser, W. O. J. "Permutations without Rising or Falling -Sequences." Ann. Math. Statist.38, 1245-1254,
1967.André, A. A. "Unranking -Avoiding Permutations with Two Forbidden Offsets." 9
Oct 2026. https://arxiv.org/abs/2610.23958.Ball,
W. W. R. and Coxeter, H. S. M. Mathematical
Recreations and Essays, 13th ed. New York: Dover, p. 50, 1987.Carlitz,
L. "Congruences for the Ménage Polynomials." Duke Math. J.19,
549-552, 1952.Carlitz, L. "Congruence Properties of the Ménage
Polynomials." Scripta Math.20, 51-57, 1954.Cayley,
A. "On a Problem of Arrangements." Proc. Roy. Soc. Edinburgh9,
338-342, 1878.Cayley, A. "Note on Mr. Muir's Solution of a Problem
of Arrangements." Proc. Roy. Soc. Edinburgh9, 388-391, 1878.Comtet,
L. "The 'Problème des Ménages.' " §4.3 in Advanced
Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht,
Netherlands: Reidel, pp. 183-185, 1974.Dörrie, H. "Lucas'
Problem of Married Couples." §8 in 100
Great Problems of Elementary Mathematics: Their History and Solutions. New
York: Dover, pp. 27-33, 1965.Gilbert, E. N. "Knots and
Classes of Ménage Permutations." Scripta Math.22, 228-233,
1956.Kaplansky, I. "Solution of the 'Problème des Ménages.'
" Bull. Amer. Math. Soc.49, 784-785, 1943.Kaplansky,
I. and Riordan, J. "The Problème des Ménages." Scripta
Math.12, 113-124, 1946.Kerawala, S. M. "Asymptotic
Solution of the 'problème des Ménages.' " Bull. Calcutta Math.
Soc.39, 82-84, 1947.Lucas, E. Théorie
des nombres. Paris, France: pp. 215 and 491-495, 1891. Reprinted, A. Blanchard,
1979.MacMahon, P. A. Combinatory
Analysis, Vol. 1. London, England: Cambridge University Press, pp. 253-256,
1915.Newman, D. J. "A Problem in Graph Theory." Amer.
Math. Monthly65, 611, 1958.Renteln, P. "Permanents,
Matchings, Symmetric Group Characters, and the Problème des Ménages."
Elec. J. Combin.33, P3.73, 2026. https://doi.org/10.37236/15190.Riordan,
J. "The Arithmetic of Ménage Numbers." Duke Math. J.19,
27-30, 1952.Riordan, J. An
Introduction to Combinatorial Analysis. New York: Wiley, pp. 195-201,
1980.Schöbe, W. "Das Lucassche Ehepaarproblem." Math.
Z.48, 781-784, 1943.Schöbe, W. "Zum Lucasschen
Ehepaarproblem." Mitt. Verein. Schweiz. Versich.-Math.61, 285-292,
1961.Sloane, N. J. A. Sequences A000179/M2062
and A000904, and A354152
in "The On-Line Encyclopedia of Integer Sequences."Taylor,
H. M. Messenger Math.32, 1903.Touchard, J. "Sur
un problème de permutations." C. R. Acad. Sci. Paris198,
631-633, 1934. https://gallica.bnf.fr/ark:/12148/bpt6k31506/f631.item.Touchard,
J. "Permutations Discordant with Two Given Permutations." Scripta Math.19,
108-119, 1953.Vardi, I. Computational
Recreations in Mathematica. Reading, MA: Addison-Wesley, 1991.Wyman,
M. and Moser, L. "On the problème des ménages." Canad.
J. Math.10, 468-480, 1958.
married couples can be seated around a circular table with men and women alternating
and no person next to their spouse. The solution (Ball and Coxeter 1987, p. 50)
uses discordant permutations and was solved
by Laisant, Moreau, and Taylor. The reduced numbers 
satisfy Laisant's
recurrence formula
,
with 
and 
(Dörrie 1965, p. 33).
in terms of a sum due to Touchard (1934) is
is a binomial coefficient (Comtet 1974, p. 185;
Vardi 1991, p. 123).
for 
, 3, ... obtained from the recurrence
relation and sum above are 0, 1, 2, 13, 80, 579, ... (OEIS A000179),
which are sometimes called ménage numbers. For 
labeled seats, the total is 
. If seatings differing only by a rotation
are identified, the count is 
. The numbers 
can be considered a special case of a restricted rooks
problem.
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
is the permanent. More generally, for each permutation 
,
let 
be its permutation matrix and define
is constant on each conjugacy
class. Its Frobenius characteristic is the symmetric
function
is the Schur function indexed by the partition 
.
Writing 
for the coefficient of 
, Renteln (2026) proves
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
,
with 
and 
.
For 
,
when 
is an n-cycle, 
is conjugate to 
, so the reduced ménage number is
and 
rather than 0 and 1. For 
, let 
count permutations 
of 
satisfying 
for every 
.
With 
,
the values for 
,
1, 2, ... are 1, 0, 1, 1, 4, 13, 82, 579, 4740, ... (OEIS A354152).
André (2026) proved that 
for odd 
and 
for even 
, settling the latter relation, which had been conjectured.
André (2026) also gave polynomial-time ranking and unranking algorithms when
any two distinct offsets modulo 
are forbidden.
-Sequences." Ann. Math. Statist. 38, 1245-1254,
1967.André, A. A. "Unranking 
-Avoiding Permutations with Two Forbidden Offsets." 9
Oct 2026.