Inspired by these questions:
- Probability of Couples sitting next to each other (Sitting in a Row)
- Probability question about married couples
- Four married couples, eight seats. Probability that husband sits next to his wife?
- In how many ways can n couples (husband and wife) be arranged on a bench so no wife would sit next to her husband?
- No husband can sit next to his wife in this probability question
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?
Best Answer
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.