Find the number of ways $v_n$ of seating $n$ couples around a rectangular table such that no one is allowed to sit across from his or her partner,figure $(\text{I})$.
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$
$$\text{Figure (I)}$$
First we should find the number of ways that $2n$ people can sit around the table,we choose $n$ of $2n$ people to sit on one of the sides of the table in $\binom{2n}{n}$ ways,besides for the people sitting on each sides of the table there are $n!$ permutations,and so by the multiplicative law:$$\binom{2n}{n}\left(n!\right)^{2}=\left(2n\right)!$$
Denote by $w_k$ the number of seatings under which some specified set of $k$ couples (and possibly some other couples) end up sitting across from their partner:
$$v_n=\left|\bigcap_{i=1}^{n}\overline{A_i}\right|=\left(2n\right)!-\left|\bigcup_{i=1}^{n}A_i\right|=\sum_{k=0}^{n}\left(-1\right)^{k}\binom{n}{k}w_{k}$$
Now it's left to determine a formula for $w_k$:
$$w_k=k!\cdot2^{k}\binom{2n-2k}{n-k}\left(n-k\right)!^{2}$$
(Decide which couple goes where, and which partner takes which seat, and where the $2n-2k$ individuals go.)
It can be thought as moving $k$ identical non-overlapping dominoes on $2n$ labelled vertices arranged in a rectangle ,figure $(\text{II})$.
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$
$$\text{Figure (II)}$$
Plugging $w_k$ into the main formula follows:
$$v_n=n!\sum_{k=0}^{n}\left(-1\right)^{k}\binom{2n-2k}{n-k}\left(n-k\right)!2^{k}$$
That was what I tried,however my combinatorics is not good at all and I want someone to check the process and give me a proof if that's wrong,thanks.
Best Answer
You were almost by the correct answer. In any case your reasoning was correct. However you should observe that the sentence:
"Decide which couple goes where"
corresponds to the number $$ \frac{n!}{(n-k)!}=\binom nkk! $$ rather than $k!$.
Therefore the correct values are: $$w_k=n!\cdot2^{k}\binom{2n-2k}{n-k}\left(n-k\right)!$$ and $$v_n=(n!)^2\sum_{k=0}^{n}\left(-1\right)^{k}\binom{2n-2k}{n-k}\frac{2^{k}}{k!}.$$