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.

Inspired by these questions:

the more general question of the probability that seating $n$ couples (i.e. $2n$ individuals) in a row at random means that no couples are sat together can be expressed using inclusion-exclusion as

$$\displaystyle\sum_{i=0}^n (-2)^i {n \choose i}\frac{(2n-i)!}{(2n)!}$$

which for small $n$ takes the values:

n   Probability of no couple together           
1   0           0   
2   1/3         0.3333333
3   1/3         0.3333333
4   12/35       0.3481481
5   47/135      0.3428571   
6   3655/10395  0.3516114
7   1772/5005   0.3540460
8   20609/57915 0.3558491

This made me wonder whether it converges to $e^{-1} \approx 0.3678794$ as $n$ increases, like other cases such as the secretary/dating problem and $\left(1-\frac1n\right)^n$ do. So I tried the following R code (using logarithms to avoid overflows)

couples  <- 1000000
together <- 0:couples
sum( (-1)^together * exp( log(2)*together + lchoose(couples,together) + 
     lfactorial(2*couples - together) - lfactorial(2*couples) ) ) 

which indeed gave a figure of $0.3678794$.

How might one try to prove this limit?

share|improve this question
1  
We give a wrong argument. Call a woman happy if her partner does not sit next to her. The probability a woman is happy turns out to be the surprisingly simple $1-\frac{1}{n}$. Now take the $n$-th power. Of course we can't do that, the events are not quite independent. –  André Nicolas Aug 11 '13 at 22:16

3 Answers 3

up vote 1 down vote accepted

I observe that each term with $i$ fixed approaches a nice limit. We have

$$ 2^i \frac{n(n-1)(n-2)\cdots(n-i+1)}{i!} \frac1{(2n-i+1)(2n-i+2)\cdots(2n)} $$

or

$$ \frac1{i!} \frac{2n}{2n} \frac{2(n-1)}{2n-1} \cdots \frac{2(n-i+1)}{(2n-i+1)} \sim \frac 1{i!} $$

This gives you the series, assuming the limits (defining terms with $i>n$ to be zero) may be safely exchanged,

$$\lim_{n\to\infty} \sum_{i=0}^\infty [\cdots] = \sum_{i=0}^\infty \lim_{n\to\infty} [\cdots] = \sum_{i=0}^\infty (-1)^i \frac1 {i!} \equiv e^{-1}$$

Justifying the limit interchange I haven't thought about but I suspect this can be shown to be fine without too much effort... Edit: You can probably use the Weierstrass M-test.

share|improve this answer
    
That works for me: each term is (ignoring signs) less than or equal to $1/i!$ so the absolute sum of the terms with $i \gt k$ is less than $1/k!$ and the remaining finite number of terms (ignoring signs) each converges to $1/i!$. Then increase $k$. –  Henry Aug 12 '13 at 14:37
    
@Henry Something like that P: Thanks for the fix. –  Sharkos Aug 12 '13 at 23:04

Let $a_n=\sum_{i=0}^n (-2)^i {n \choose i}\frac{(2n-i)!}{(2n)!}$, let $b_n=(1-\frac{1}{n})^n$, and let $c_n=\sum_{i=0}^n (-1)^i \frac{1}{i!}$.
We will show below that $b_n\le a_n\le c_n$ for $n\ge2$, so then we can conclude that $\displaystyle\lim_{n\to\infty}a_n=\frac{1}{e}$
by the Squeeze Theorem since $\displaystyle\lim_{n\to\infty}b_n=\frac{1}{e}$ and $\displaystyle\lim_{n\to\infty}c_n=\frac{1}{e}$.

$\textbf{1)}$ To show that $a_n\le c_n$ for $n\ge 2$, let $$c_n-a_n=\sum_{i=0}^n (-1)^i \frac{1}{i!}-\sum_{i=0}^n (-2)^i {n \choose i}\frac{(2n-i)!}{(2n)!}$$ $$=\sum_{i=0}^n (-1)^i\frac{1}{i!}\bigg[1-\frac{2^{i}n!}{(n-i)!}\frac{(2n-i)!}{(2n)!}\bigg]=\sum_{i=0}^n(-1)^it_i,$$where $t_i=\frac{1}{i!}\bigg[1-\frac{2^{i}n!}{(n-i)!}\frac{(2n-i)!}{(2n)!}\bigg]>0$ for $i\ge 2$ since $\frac{2^{i}n!}{(n-i)!}\frac{(2n-i)!}{(2n)!}=\frac{(2n)(2n-2)(2n-4)\cdots(2n-2i+2)}{(2n)(2n-1)(2n-2)\cdots(2n-i+1)}<1$.

Therefore to show that $c_n-a_n\ge0$ for $n\ge2$, it suffices to show that

$t_{i}-t_{i+1}\ge0$ for any even integer $i\ge2$:

$$\displaystyle t_{i}-t_{i+1}=\frac{1}{i!}\bigg[1-\frac{2^{i}n!}{(n-i)!}\frac{(2n-i)!}{(2n)!}\bigg]-\frac{1}{(i+1)!}\bigg[1-\frac{2^{i+1}n!}{(n-i-1)!}\frac{(2n-i-1)!}{(2n)!}\bigg]$$ $$\displaystyle=\frac{1}{(i+1)!}\bigg[i+1-\frac{(i+1)2^{i}n!(2n-i)!}{(n-i)!(2n)!}-1+\frac{2^{i+1}n!(2n-i-1)!}{(n-i-1)!(2n)!}\bigg]$$ $$\displaystyle=\frac{1}{(i+1)!}\bigg[i-\frac{(i+1)2^{i}n!(2n-i)!}{(n-i)!(2n)!}+\frac{2^{i+1}(n-i)n!(2n-i-1)!}{(n-i)!(2n)!}\bigg],$$

so $t_{i}-t_{i+1}\ge0 \iff$ $$ i(n-i)!(2n)!\ge(i+1)2^{i}n!(2n-i)!-2^{i+1}(n-i)n!(2n-i-1)!$$

$$\\\ \;\;\;\;\; =\ 2^{i}n!(2n-i-1)!\big[(i+1)(2n-i)-2(n-i)\big]$$ $$\\\ \;\;=2^{i}n!(2n-i-1)!(i)(2n-i+1)\iff$$ $$(n-i)!(2n)!\ge2^{i}n!(2n-i-1)!(2n-i+1)\iff$$ $$\big[(2n)(2n-1)(2n-2)\cdots(2n-i+2)\big](2n-i)\ge2^{i}n(n-1)(n-2)\cdots(n-i+1)\iff$$ $$\big[(2n)(2n-1)(2n-2)\cdots(2n-i+2)\big](2n-i)\ge(2n)(2n-2)(2n-4)\cdots(2n-2i+2),$$ which is clearly true for any even integer $i\ge2$.

$-------------------------------------------$

$\textbf{2)}$ To show that $a_n\ge b_n$ for $n\ge2$, we can use the Binomial Formula and then proceed as above:

Let $$a_n-b_n=\sum_{i=0}^n (-2)^i {n \choose i}\frac{(2n-i)!}{(2n)!}-\sum_{i=0}^n {n\choose i}\big(\frac{-1}{n}\big)^i$$ $$=\sum_{i=0}^n (-1)^{i} \frac{1}{i!}\bigg[\frac{2^{i}n!(2n-i)!}{(n-i)!(2n)!}-\frac{n!}{(n-i)!(n^{i})}\bigg]=\sum_{i=0}^n(-1)^i s_i,$$ where $s_i=\frac{1}{i!}\bigg[\frac{2^{i}n(n-1)\cdots(n-i+1)}{(2n)(2n-1)\cdots(2n-i+1)}-\frac{n(n-1)\cdots(n-i+1)}{n^i}\bigg]>0$ for $i\ge2$ since $\;\;\;\;2^{i}n^{i}=(2n)^{i}\ge(2n)(2n-1)(2n-2)\cdots(2n-i+1).$

Therefore to show that $a_n-b_n\ge0$ for $n\ge2$,

it suffices to show that $s_{i}-s_{i+1}\ge0$ for any even integer $i\ge2$:

$$s_{i}-s_{i+1}=\frac{1}{i!}\bigg[\frac{2^{i}n(n-1)\cdots(n-i+1)}{(2n)(2n-1)\cdots(2n-i+1)}-\frac{n(n-1)\cdots(n-i+1)}{n^i}\bigg]-\frac{1}{(i+1)!}\bigg[\frac{2^{i+1}n(n-1)\cdots(n-i)}{(2n)(2n-1)\cdots(2n-i)}-\frac{n(n-1)\cdots(n-i)}{n^{i+1}}\bigg]$$ $=\frac{1}{(i+1)!}\bigg[\frac{2^{i}(i+1)n(n-1)\cdots(n-i+1)}{(2n)(2n-1)\cdots(2n-i+1)}-\frac{(i+1)n(n-1)\cdots(n-i+1)}{n^i}-\frac{2^{i+1}n(n-1)\cdots(n-i)}{(2n)(2n-1)\cdots(2n-i)}+\frac{n(n-1)\cdots(n-i)}{n^{i+1}}\bigg]$ $=\frac{1}{(i+1)!}\bigg[\frac{2^{i}(i+1)(2n-i)n(n-1)\cdots(n-i+1)}{(2n)(2n-1)\cdots(2n-i)}-\frac{(n-1)(n-2)\cdots(n-i+1)[n(i+1)-(n-i)]}{n^i}\bigg]$,so

$s_i-s_{i+1}\ge0\iff$ $2^{i}n^{i}(i+1)(2n-i)n(n-1)(n-2)\cdots(n-i+1)\ge i(n+1)(n-1)(n-2)\cdots(n-i+1)(2n)(2n-1)\cdots(2n-i)\iff$ $$2^{i}n^{i}(i+1)(2n-i)n\ge i(n+1)(2n)(2n-1)(2n-2)\cdots(2n-i)\iff$$ $$(2n)^{i}(i+1)n\ge i(n+1)(2n)(2n-1)(2n-2)\cdots(2n-i+1),$$ and this inequality is valid since $(i+1)n\ge i(n+1)$ and $(2n)^{i}\ge (2n)(2n-1)(2n-2)\cdots(2n-i+1)$.

share|improve this answer

Without loss of generality, suppose everyone is sitting in a circle instead of a row and that there is one unoccupied seat. For each wife, the probably that her husband is not sitting next to her on either side is $1 - \frac{2}{2 \cdot n}$ and there are $n$ wives, so the probability that no wife is sitting next to her husband is $(1- \frac{1}{n})^n$, whose limit is the definition of $\frac{1}{e}$.

share|improve this answer
2  
This is similar to André Nicolas's comment, and so I think it has the same "not quite independent" issue he raises –  Henry Aug 12 '13 at 7:33

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.