# Arranging Couples in a Row

Three couples are sitting in a row. Compute the number of arrangements in which no person is sitting next to his or her partner. Answer is 240.

From wikipedia, This problem is called the menage problem have a fourmula called Touchard's formula:

Let $M_n$ denote the number of seating arrangements for n couples. Touchard (1934) derived the formula

$M_n = 2 \cdot n! \sum_{k=0}^n (-1)^k \frac{2n}{2n-k} {2n-k\choose k} (n-k)!$

How does one mnage to prove it

• Touchard's formula, see en.wikipedia.org/wiki/Ménage_problem, applies to couples sitting around a table, not couples sitting in a row. Try it for $n=3$; do you get 240? – Gerry Myerson Feb 19 '12 at 1:07
• There's a very nice discussion of Touchard at math.dartmouth.edu/~doyle/docs/menage/menage/menage.html. As I say, Touchard isn't what you want, but the ideas at that site might apply to the row situation. – Gerry Myerson Feb 19 '12 at 1:12
• – Henry Feb 19 '12 at 1:22
• As suggested by Gerry, this can be related to the relaxed Menage problem as described by Bogart at the Dartmouth link. Let $m_n$ be the result of the relaxed Menage problem as described by Bogart, and let $M_n$ be as defined by the OP. Then $M_n=nM_{n-1}+m_n$ for $n\ge 1$. This is because every solution of the relaxed menage problem can be made into a solution of the OP's problem by "cutting" the circular table at a fixed point, but in addition to these solutions we have solutions where the two members of a couple are seated at opposite ends of the linear table. – Ben Crowell Feb 19 '12 at 2:16
• Oops, the above should be $M_n=2nM_{n-1}+m_n$. – Ben Crowell Feb 19 '12 at 2:33

There are $(2n)!$ ways of getting $2n$ people to sit in a row. If we wanted all aof them to sit as couples there would be $n!$ ways of arranging the couples and $2^n$ ways of arranging within the couples.

If we require $k$ named couples to sit together then this becomes $(2n-k)$ units to arrange, giving $(2n-k)!$ possibilities. There are $2^k$ ways to arrange within the named couples. But there are ${n \choose k}$ ways of naming the couples. So this gives $2^k{n \choose k}(2n-k)!$.

That previous figure will involve double counting so we need to use inclusion-exclusion to answer your question and get $$(2n)! - 2^1{n \choose 1} (2n-1)!+ 2^2{n \choose 2} (2n-2)! - \cdots 2^k{n \choose k} (2n-k)! \cdots 2^n n!$$ $$=\sum_{k=0}^n (-2)^k{n \choose k} (2n-k)!$$

and for $n=3$ this gives $720-720+288-48=240$.

• Since we want to sit couples and not people, why wouldn't it be $n!$ minus everything else? Also, is this equal to $\frac {(2n)!} {e}$? – shinzou Apr 14 '15 at 16:15
• @kuhaku: We want to seat people (explicitly not couples) and there are $2n$ people. The number of ways is an integer so not exactly $\dfrac{(2n)!}{e}$, though for large $n$ the proportion with no couples approaches $\dfrac1e$. See another question for a proof – Henry Apr 14 '15 at 16:29
• If we wanted to sit couples, would it be $n!$ then? – shinzou Apr 14 '15 at 16:48
• @kuhaku: More like $2^n n!$ as each couple can sit in two ways (swap the two individuals round) – Henry Apr 14 '15 at 16:50
• I meant sitting $n$ couples such that no women sits with her spouse. – shinzou Apr 14 '15 at 16:51

This is (the $n=3$ term in) http://oeis.org/A007060, "Number of ways n couples can sit in a row without any spouses next to each other." There are some formulas and links there that may be helpful.

I don't know how to do it without a certain amount of brute force, but you can reduce the possibilities. Call the six Mr. and Mrs. A, B, C. By symmetry, it doesn't matter who starts, so let's say Mr. A and multiply by 6 at the end. Then you have 4 choices for the second slot and they are all the same, so say Mrs. B. For the third slot you have two types of possibilities-you have have Mrs. A (one choice) or Mr. or Mrs. C(two choices). The difference is that Mrs. A imposes no restriction on the fourth seat. If it is Mrs A, you have two ways to fill the remaining seats because you have BCC left and have to separate the C's. If one of the C's, you have 4 because you have ABC left and can't start with C. So there are a total of 6*4*(1*2+2*4)=240 possibilities.

[EDIT] The OP originally posted the $n=3$ case, then changed the question to ask for a general result. This was in response to the $n=3$ question.

Here is a method with slightly less brute force than Ross Millikan's. Impose two extra rules: (1) that each couple must be introduced in alphabetical order, and (2) that each woman must come before her partner. Imposing these rules cuts the number of possibilities by a factor of $6\times 8$. Under these rules, there are two possible patterns for the sexes: FFFMMM (one possibility), and FFMFMM (four possibilities, since there are two choices for the fourth person, and then two ways of ordering the remaining two). The total number of possibilities is then $6\times8\times(1+4)=240$.