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