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$.

-

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.

-

[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$.

-

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.

-