1
$\begingroup$

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

  • 0
    Another related: http://math.stackexchange.com/questions/465318/showing-probability-no-husband-next-to-wife-converges-to-e-12014-03-19

4 Answers 4

5

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

  • 0
    @kuhaku: To repeat myself, that is seating $2n$ people (explicitly not couples)2015-04-14
2

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.

1

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.

1

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