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
with
and
(Dörrie 1965, p. 33).
A closed form expression for in terms of a sum due to Touchard (1953) is
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.
Abramson, M. and Moser, W. O. J. "Permutations Without Rising or Falling -Sequences." Ann. Math. Statist.38, 1245-1254,
1967.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: pp. 215 and 491-495, 1891. Reprinted, A. Blanchard,
1979.MacMahon, P. A. Combinatory
Analysis, Vol. 1. London: Cambridge University Press, pp. 253-256,
1915.Newman, D. J. "A Problem in Graph Theory." Amer.
Math. Monthly65, 611, 1958.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. Sequence A000179/M2062
in "The On-Line Encyclopedia of Integer Sequences."Taylor,
H. M. Messenger Math.32, 1903.Touchard, J. "Sur
un problème de permutations." Comptes Rendus Acad. Sci. Paris198,
631-633, 1943.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 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
and 
(Dörrie 1965, p. 33).
in terms of a sum due to Touchard (1953) is
is a binomial coefficient (Comtet 1974, p. 185;
Vardi 1991, p. 123).
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.
-Sequences." Ann. Math. Statist. 38, 1245-1254,
1967.Ball, W. W. R. and Coxeter, H. S. M.