In how many ways can n couples (husband and wife) be arranged on a bench so no wife would sit next to her husband?
I thought about this:
(Total amount of ways to sit 2n people in 2n sits)-(Using inclusion and exclusion to find that at least 1 wife sits next to her husband) And i get:
Let $A_1$ be the attribute where at least 1 wife sits with her husband, Then we "merge" up the husband and wife into a one person. We have $\binom n1$ ways to choose $1$ couple out of $n$ couples, And we are left with $2n-1$ to place $2n-1$ 'people' so we get $(2n-1)!$ and so on, And on a general note:
$(2n)!-(2\binom n1(2n-1)!-2^2\binom n2(2n-2)!+…2^k(-1)^k\binom nk(2n-k)!)$ And a bit simplified:
$(2n)!-(\sum_{k=1}^n2^k(-1)^k\binom nk(2n-k)!$)
Since i don't have answers to this question i wanna know if i did something wrong? Did i even look at the question right?
Best Answer
As far as I am able to tell, the answer is correct.
After some unsuccessful attempts at simplifying the resulting expression, I went ahead and asked Wolfram for the answer. He came up with the formula:
$$ 4^n \frac{\Gamma(n+\frac{1}{2})}{\sqrt{\pi}} \operatorname{Hypergeometric1F1}(-n,-2n,-2)$$
The weird looking term $\frac{\Gamma(n+\frac{1}{2})}{\sqrt{\pi}} $ is just $(2n-1)!!/2^n$, so this can also be written as:
$$ 2^n (2n-1)!! \cdot \operatorname{Hypergeometri1cF1}(-n,-2n,-2)$$
Unfortunately, it seems that $\operatorname{Hypergeometri1cF1}(-n,-2n,-2)$ is not anything nicer. Of course, I only have heuristic justification of the type "if it was something nicer, it wouldn't be called with such scary name, and Wolfram would be able to simplify it".