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 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_1=A_2=1$. A closed form expression due to Touchard (1934) is

$$A_n=\sum_{k=0}^n {2n\over 2n-k}{2n-k\choose k}(n-k)!(-1)^k,$$

where ${n\choose k}$ is a Binomial Coefficient (Vardi 1991).

The first few values of $A_n$ are $-1$, 1, 0, 2, 13, 80, 579, ... (Sloane's 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 Discordant Permutation, Laisant's Recurrence Formula, Rooks Problem

References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, p. 50, 1987.

Dörrie, H. §8 in 100 Great Problems of Elementary Mathematics: Their History and Solutions. New York: Dover, pp. 27-33, 1965.

Halmos, P. R.; Vaughan, H. E. ``The Marriage Problem.'' Amer. J. Math. 72, 214-215, 1950.

Lucas, E. Théorie des Nombres. Paris: A. Blanchard, pp. 215 and 491-495, 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.

Sloane, N. J. A. Sequence A000179/M2062 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Touchard, J. ``Sur un problème de permutations.'' C. R. Acad. Sci. Paris 198, 631-633, 1934.

Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, p. 123, 1991.