11
$\begingroup$

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?

$\endgroup$
14
  • 1
    $\begingroup$ $2n$ people can sit in $2n$ seats in $(2n)!$ ways, not $(2n)^{2n}$. $\endgroup$
    – Arthur
    May 14, 2013 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$ May 14, 2013 at 19:39
  • 1
    $\begingroup$ One minor thing: last sum is either from $k = 1$, or skip the term $2n!$ in front. $\endgroup$ May 14, 2013 at 20:07
  • 2
    $\begingroup$ You actually can just do the sum from $0$ and omit the $(2n)!$ $\endgroup$
    – NightRa
    Sep 3, 2013 at 17:06
  • 3
    $\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, 2018 at 16:09

1 Answer 1

0
$\begingroup$

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

$\endgroup$

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.