# Showing probability no husband next to wife converges to $e^{-1}$

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?

-
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

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.

-
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

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}$.

-
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

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)$.

-