Lucas' Problem of the Married Couples

I've seen this problem before but I thought it interesting to revisit it and look at its historical background. This is Problem 8 in "100 Great Problems of Elementary Mathematics" by Heinrich Dörrie. The problem is stated as follows:

How many ways can \(n\) married couples be seated about a round table in such a manner that there is always one man between two women and none of the men is ever next to his own wife?

This problem appeared (probably for the first time) in 1891 in the Theorie des Nombres of the French mathematician Edouard Lucas (1842-1891), author of the famous work Récréations mathématiques. The English mathematician Rouse Ball has said of this problem, “The solution is far from easy.” The problem has been solved by the Frenchmen M. Laisant and M. C. Moreau and by the Englishman H. M. Taylor. A solution based upon modern viewpoints is to be found in MacMahon’s Combinatory Analysis. The approach adopted here is essentially that of Taylor (The Messenger of Mathematics, 32, 1903).

I spent quite some time, on and off, attempting my own solution before coming up short. It was a useful exercise however, because I explored various approaches and the most promising to me seemed to be one involving Cartesian products, so I got a fair bit of practice in working with these products. Once again I was trying for a brute force approach using SageMathCell to create all possible permutations and then imposing progressive restrictions on these permutations. However, the number of permutations quickly become huge and SageMathCell timed out for \(n=5\) and beyond.

According to WolframMathWorld, a closed form expression for \(n>1\) in terms of a sum due to Touchard (1953) is:$$A_n=\sum_k ^n \frac{2n}{2n-k} \binom{2n-k}{k} (n-k)! \, (-1)^k$$Once the formula is known it's easy enough to execute in SageMathCell. Here is the permalink to the calculation up to \(n=10\). The reason I'm quoting from WolframMathWorld and not the original book is that the explanation runs for several pages. Quite simply, as Rouse Ball put it, "the solution is far from easy". Wikipedia gives a simple, four-term recurrence (here is a permalink to the SageMathCell execution of it): $$ A_n = n \, A_{n-1}+2 \, A_{n-2}-(n-4) \, A_{n-3} - A_{n-4} $$ $$ \text{ with } A_2=0, A_3=1,A_4=2,A_5=13$$Wikipedia refers to this sequence of numbers as the mènage numbers and they form OEIS A000179, shown here for \(n=2 \text{ to } 10\):$$0, 1, 2, 13, 80, 579, 4738, 43387, 439792, ... $$It's clear that the number of arrangements increases at a very rapid rate. For just ten couples, there are almost half a million possibilities. The problem has connections with graph theory, knot theory and even chess (see Rooks Problem) but overall I found the problem rather too daunting and didn't have the patience or motivation to wade through the explanation in the book.

However, I'll quote the basis of the book's explanation:

The wives will then all have to be seated on the even- or odd-numbered chairs. In each of these two cases there are \(n!\) dif­ferent possible seating arrangements, so that there are \(2n!\) different possible seating arrangements for the women alone. We will assume that the women have been seated in one of these arrangements and we will maintain this seating arrangement through­ out the following. The nucleus of the problem then consists of deter­mining the number of possible ways of seating the men between the women.

Let us designate the women in the assumed seating sequence as \(F_1, F_2, ..., F_n \), their respective husbands \(M_1, M_2, ...,M_n\), the couples \( (F_1, M_1), (F_2,M_2),...,\) as \(1,2,...\) and the arrangements in which there are \(n\) married couples as \(n\)-pair arrangements. Let us designate the husbands about whom we have no further information as \(X_1, X_2, ...\).

Let \(F_1X_1F_2X_2,...,F_nX_n,F_{n+1}X_{n+1} \) be an (\(n+1)\)-pair arrangement in which none of the husbands sits beside his own wife. It must be remembered that the arrangement is circular, so that \(X_{n+1}\) is seated between \(F_{n+1}\) and \(F_1\). If we take \(F_{n+1}\) and \(M_{n+1}=X_{\nu}\) out of the arrangement and replace \(X_{\nu} \) with \(X_{n+1}=M_{\mu}\), we obtain the \(n\)-pair arrangement: $$F_1X_1F_2X_2...F_{\nu}M_{\mu}F_{\nu+1}...F_nX_n $$This arrangement can occur in three ways:

1. No man sits next to his wife (thus \( M_{\mu} \neq M_{\nu},M_{\mu} \neq M_{\nu+1}, X_n \neq M_1\)).

1. One man sits next to his own wife (namely when \(M_{\mu}=M_{\nu}\) or \(M_{\mu}=M_{\nu+1}\) or else \(X_n=M_1\)).

1. Two men sit next to their own wives (when \(M_{\mu}=M_{\nu}\) or \(M_{\mu}=M_{\nu+1}\) and at the same time \(X_n=M_1\), that is, when in our arrangement the order \(M_1F_1\) occurs.

It goes on and on from there but that's the start of the explanation anyway. On looking further ahead in the book, it seems that in general the problems are rather too difficult for a recreational mathematician to approach. For that reason, I may go back to Project Euler of which I've solved only 8 out of the 723 available problems. These problems are mathematical and require a programming solution.