A round table with no couple together

Five couples come to dinner at a round table with ten chairs. The host wants men and women to alternate, and nobody to sit beside the person they came with. In how many ways can that be done?

The question was put in this form by Édouard Lucas in 1891, in his book on the theory of numbers, and it has been called the problème des ménages — the problem of the households — ever since. It sounds like a puzzle for a dinner party. It turned out to need an idea that took another half-century to find, and the idea is a single observation about which forbidden cells can attack which.

Seat the women first #

The count splits cleanly into two stages. The women can take the alternate chairs in $2 \times 5!$ ways: two choices of which set of five chairs is theirs, and then any order. Once they are seated, the table is fixed as far as the men are concerned, and each man has exactly two chairs he may not take — the ones on either side of his partner.

So the answer is $2 \times n!$ times the number of ways to seat the men, and the men’s problem is a permutation problem. There are $n$ men and $n$ gaps between women; each man must go to a gap; and man $i$ is forbidden from two particular gaps. Every other structure of the table has dropped away.

For five couples the men have $13$ good arrangements, and the total is $2 \times 120 \times 13 = 3{,}120$. For three couples the men have exactly one — each man has only one gap left that is not beside his partner — and for four they have two.

A board with a corner #

Written as a board of forbidden cells, the tool that counts permutations with forbidden positions, the men’s problem has a shape.

The band of width two appeared at the end of the essay on boards, where its avoidance was shown settling on $e^{-2}$. What the round table adds is the corner: the last row’s second forbidden cell wraps round to the first column. A straight bench with couples at alternate places would give the band without the corner, and the corner changes the count from $16$ to $13$.

The corner looks like a small perturbation and is actually the whole structure. It turns the band from a path of forbidden cells into a cycle, and the problem is to count rook placements on a cycle.

Forbidden cells that attack round a ring #

Read the forbidden cells of the round board in order: $(1,1)$, $(1,2)$, $(2,2)$, $(2,3)$, and so on down the band, ending with $(n,n)$, $(n,1)$ and back to $(1,1)$. Each cell shares its row with the cell before it or after it, and its column with the other one. It shares a row or a column with nothing else.

So two forbidden cells attack each other exactly when they are neighbours on this ring of $2n$ cells. A placement of $k$ non-attacking rooks is then just a choice of $k$ cells on a circle with no two adjacent, and the rook numbers are a purely one-dimensional count. That observation is Irving Kaplansky’s, published in 1943, and it is what made the problem easy.

The count of non-adjacent choices is a small exercise. On a path of $m$ points, choosing $k$ with no two adjacent is the same as choosing $k$ from $m - k + 1$, because each chosen point after the first uses up one extra gap: the number is $\binom{m-k+1}{k}$. On a cycle of $m$ points, look at one particular point. If it is chosen, its two neighbours are excluded and the rest is a path of $m - 3$ points needing $k - 1$ more, which gives $\binom{m-k-1}{k-1}$. If it is not chosen, the rest is a path of $m - 1$ points needing $k$, which gives $\binom{m-k}{k}$. The two add to

$$\binom{m-k-1}{k-1} + \binom{m-k}{k} = \frac{m}{m-k}\binom{m-k}{k}.$$

With $m = 2n$ these are the rook numbers of the round board, and the straight bench, whose forbidden cells form a path of $2n - 1$, has rook numbers $\binom{2n-k}{k}$ instead. That difference, one cell and the join it makes, is the difference between thirteen and sixteen.

The two sums can be set side by side for five couples. The bench’s rook numbers are $1, 9, 28, 35, 15, 1$ and give $120 - 216 + 168 - 70 + 15 - 1 = 16$. The round table’s are $1, 10, 35, 50, 25, 2$ and give $120 - 240 + 210 - 100 + 25 - 2 = 13$. Every rook number grows when the ring closes, because the extra cell adds placements, and yet the count falls — the alternating signs turn more ways to break the rule into fewer ways to keep it. The last rook number is the most telling: a path of nine cells holds only one set of five non-adjacent cells, the alternate ones starting at an end, while a ring of ten holds two, the odd cells and the even ones. Those are the two complete seatings in which every man sits beside his partner — all of them to their partner’s left, or all to the right.

Touchard’s formula #

Now the inclusion–exclusion step from the board essay applies unchanged. The number of ways to seat the men is

$$U_n = \sum_{k=0}^{n} (-1)^k \, \frac{2n}{2n-k}\binom{2n-k}{k}\,(n-k)!,$$

and the answer to Lucas’s question is $2 \cdot n! \cdot U_n$.

The formula is usually credited to Jacques Touchard, who stated it in 1934, and it had a long prehistory. Peter Guthrie Tait had met a version of the question in the 1870s, in his work on knots, and Arthur Cayley and Thomas Muir found recurrences for the relaxed count in 1878 and the years after. Lucas’s own solution of 1891 was a recurrence too. Each of these was a separate argument, and none generalised. Kaplansky’s cycle observation reduced the whole problem to inclusion–exclusion plus a count a student could do, and three years later he and John Riordan built rook theory to do the same for every board of this kind.

The running totals in the table swing between $-720$ and $720$ before settling on $80$, just as the board totals did. The largest term here is $1{,}440$, eighteen times the answer. That is the price of an alternating sum, and the reason it works anyway is the same as before: every arrangement that puts some man beside his partner is counted with weights that cancel to zero exactly.

Stopping the sum early #

Touchard’s sum need not be finished to be useful. A sum stopped early still says something showed that the partial sums of an inclusion–exclusion alternate around the answer — too high after an even number of correction terms, too low after an odd number — and that holds for any board, because the argument never looked at which cells were forbidden.

For six couples the partial sums are $720$, $-720$, $576$, $-96$, $114$, $78$ and finally $80$. The early brackets are useless: the first pair says only that the answer lies between $-720$ and $720$, which was already known. They tighten fast from the fourth term on, and by the sixth the answer is pinned between $78$ and $114$. For a dinner of twenty couples the same bracketing lets a handful of terms fix the count to within a fraction of a per cent, without computing the rest of the sum.

That is the practical form of the result, and it is how inclusion–exclusion is actually used when the full sum is out of reach. The ménage numbers happen to have a closed formula, but the bracketing needs only the first few rook numbers, and those are available for boards that have no formula at all.

How many couples end up together #

A random seating of the men puts some number of them beside their partners, and the same rook numbers give the whole distribution. With the formula for exact hits from the board essay, eight couples give $4{,}738$ seatings with no couple together, $10{,}800$ with exactly one, $11{,}672$ with two and $7{,}888$ with three, out of $40{,}320$.

As shares those are $0.118$, $0.268$, $0.289$ and $0.196$. A Poisson count with mean two gives $0.135$, $0.271$, $0.271$ and $0.180$. The mean is exactly two at every size — each man has two forbidden gaps out of $n$, so the expected number of men beside a partner is $n imes 2/n$ — but the shape is not yet Poisson. There are too few seatings with nobody together and too many with two or three.

The distortion comes from the ring. Two forbidden cells in one row can never both be hit, and neither can two in one column — a man sits in one gap, and a gap holds one man — so hits crowd each other out. The count is therefore less spread than a Poisson count: its variance at eight couples is $12/7 \approx 1.71$ rather than $2$, and a less spread count spends less of its probability at zero. For the hats, the corresponding dependence is so weak that eight hats match the Poisson shape to four decimal places. For couples it is a correction of order $1/n$, and at twelve couples the share with nobody together has only reached $0.124$.

The chance, and how slowly it arrives #

Divide $U_n$ by $n!$ and the result is the chance that a random seating of the men, with the women fixed, puts nobody beside a partner.

The limit is $e^{-2}$, which the band essay predicted: each man has two forbidden gaps, the number of men beside their partners is close to a Poisson count with mean two, and $e^{-2}$ is its chance of being zero. The hat problem’s $1/e$ is the same statement with one forbidden place each.

What the figure shows, and the prediction did not, is how differently the two approach their limits. The hat chance is within $10^{-14}$ of $1/e$ by sixteen objects; the error is less than $1/(n+1)!$, which is why the fixed points of a shuffle matched their Poisson limit so fast. The couples’ chance at sixteen is $0.1266$, still six per cent short of $e^{-2}$, and it closes the gap only like $e^{-2}(1 - 1/n)$ — a thousand couples would still leave it a tenth of a per cent short.

The reason is visible in the rook numbers. For the hats, $r_k (n-k)!/n!$ is exactly $1/k!$ at every size, so each term of the sum is already at its limit and only the tail is missing. For the couples, $r_k (n-k)!/n!$ is $2^k/k!$ only approximately: two forbidden cells in the same row can never both be used, so adjacent cells on the ring exclude each other, and the rook numbers fall short of $\binom{2n}{k}$ by an amount of relative size about $k^2/n$. Summed over the terms, the shortfall is a correction of order $1/n$ that no finite table outgrows.

Latin rectangles are round tables #

The ménage numbers turn up somewhere that has no table in it, and the reason they do is the product rule for boards.

A three-row Latin rectangle with its first row fixed as $1, 2, \ldots, n$ has a second row that is a derangement of the first, and a third row that must avoid, in each column, the two symbols above it. So the third row is a permutation avoiding a board with two forbidden cells per row: one on the diagonal, one where the second row put its symbol.

That board splits into blocks, one for each cycle of the second row read as a permutation. A cycle of length $\ell$ contributes forbidden cells that attack round a ring of $2\ell$ — exactly a round table of $\ell$ couples — and different cycles share no row or column. So the board’s rook polynomial is the product of ménage polynomials, one per cycle, and the count of third rows is a sum over how the second row’s cycles are arranged. John Riordan carried that bookkeeping through in 1944 and got the formula in the figure. The rectangle count for seven columns, $1{,}073{,}760$ with the first row fixed, is a statement about dinner tables.

The same idea stops working at four rows: a fourth row must avoid three cells per column, and the board no longer splits into rings. That is one reason counting Latin squares is so much harder than counting their first three rows, and why the officers’ problem had to be settled by exhaustion rather than formula.

What a ring of cells cannot prove #

The rate of approach. The figure checks $e^{-2}(1 - 1/n)$ to within $1/n^2$ over fourteen sizes, and the essay explains where a correction of order $1/n$ comes from. Neither is a proof that the next term of the expansion is what the numbers suggest; that requires an asymptotic analysis of Touchard’s sum, and the pattern in a finite table is evidence rather than argument.

Why the corner costs exactly three arrangements at five couples. The difference between sixteen and thirteen is computed in the figure and explained through the rook numbers, which differ by the join between two ends of a path. What a picture of the board cannot show is which three bench arrangements the corner destroys — they are the ones that put the last man in the first gap, and seeing that requires reading the arrangements rather than the counts.

The general Latin rectangle. The rectangle table checks three rows by search up to seven columns. Riordan’s formula depends on the second row decomposing into cycles, and the pictures show neither the decomposition nor why it fails for a fourth row.

Still open: every guest beside every other, once #

The ménage problem asks how to keep certain pairs apart at one sitting. Its opposite asks how to bring every pair together exactly once over several. Suppose $2n + 1$ guests attend a conference for $n$ nights and dine at round tables of given sizes, the same sizes each night. Can they be seated so that every two guests sit side by side on exactly one night?

This is the Oberwolfach problem, posed by Gerhard Ringel in 1967 at the mathematical institute of that name, where the dining room had round tables. Four small plans are known to be impossible — two tables of three, for instance, cannot seat six guests so that every pair meets. When every table has the same size the problem was settled by 1991 apart from those exceptions, and in 2021 Stefan Glock, Felix Joos, Jaehoon Kim, Daniela Kühn and Deryk Osthus proved that every plan works once the number of guests is large enough. Computer searches have settled every plan for small numbers of guests. For the numbers between the computer searches and the unstated threshold of that theorem, whether every plan of unequal tables can be realised is open.

A dinner party solved by a circle #

Lucas’s question looked like it wanted a clever direct argument, and several were found; none extended beyond the table. The argument that lasted replaced the table with a board of forbidden cells and noticed that the round table’s forbidden cells attack each other round a ring. After that the problem was a count of non-adjacent points on a circle, and the chance of a good seating was a sum of the same shape as the hat problem’s. Nothing about the dinner survived into the solution except the one fact that the table closes up on itself.

The ring is also what makes the ménage numbers slow. Hats have one forbidden place each and reach $1/e$ at once; couples have two, joined in a ring, and reach $e^{-2}$ one factor of $1 - 1/n$ at a time. And three-row Latin rectangles, which have no dinner in them, are counted by the same rings, one for each cycle of their second row.