Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Definition of "near"? Do you mean "next to"? –  Thomas Andrews May 14 '13 at 19:36
1  
$2n$ people can sit in $2n$ seats in $(2n)!$ ways, not $(2n)^{2n}$. –  Arthur May 14 '13 at 19:37
1  
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... –  Feanor May 14 '13 at 19:39
1  
One minor thing: last sum is either from $k = 1$, or skip the term $2n!$ in front. –  Feanor May 14 '13 at 20:07
1  
You actually can just do the sum from $0$ and omit the $(2n)!$ –  NightRa Sep 3 '13 at 17:06

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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