TOPICS
Search

Married Couples Problem


Also called the ménage problem. In how many ways can n 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 n>1 can be given in terms of Laisant's recurrence formula

 (n-1)A_(n+1)=(n^2-1)A_n+(n+1)A_(n-1)+4(-1)^n,

with A_2=0 and A_3=1 (Dörrie 1965, p. 33).

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

 A_n=sum_(k=0)^n(2n)/(2n-k)(2n-k; k)(n-k)!(-1)^k,

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

The first few values of A_n for n=2, 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 2n!A_n. The numbers A_n can be considered a special case of a restricted rooks problem.


See also

Laisant's Recurrence Formula, Rooks Problem

Explore with Wolfram|Alpha

References

Abramson, M. and Moser, W. O. J. "Permutations Without Rising or Falling w-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. Edinburgh 9, 338-342, 1878.Cayley, A. "Note on Mr. Muir's Solution of a Problem of Arrangements." Proc. Roy. Soc. Edinburgh 9, 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. Monthly 65, 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. Paris 198, 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.

Referenced on Wolfram|Alpha

Married Couples Problem

Cite this as:

Weisstein, Eric W. "Married Couples Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MarriedCouplesProblem.html

Subject classifications