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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .