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?

  • 1
    $\begingroup$ $2n$ people can sit in $2n$ seats in $(2n)!$ ways, not $(2n)^{2n}$. $\endgroup$ – Arthur May 14 '13 at 19:37
  • 1
    $\begingroup$ Don't you want to have factors like $2^k{n \choose k}$ in place of ${n \choose k}$ ? You can sit husband and wife next to each other in two ways... $\endgroup$ – Jakub Konieczny May 14 '13 at 19:39
  • 1
    $\begingroup$ One minor thing: last sum is either from $k = 1$, or skip the term $2n!$ in front. $\endgroup$ – Jakub Konieczny May 14 '13 at 20:07
  • 2
    $\begingroup$ You actually can just do the sum from $0$ and omit the $(2n)!$ $\endgroup$ – NightRa Sep 3 '13 at 17:06
  • 2
    $\begingroup$ Possible duplicate of Arranging couples (husband and wife) on a bench so no wife would sit next to her husband? $\endgroup$ – inavda Aug 18 '18 at 16:09

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.