Exercise 1719Combinatorics › Inclusion-exclusionOlympiadAdded 3 Nov 2026

Derangements via double counting

#derangements#double counting#IE

Statement

Show that $D_n/n!\to1/e$ as $n\to+\infty$ .

Hint

$D_n/n!=\sum_{k=0}^{n}(-1)^k/k!\to e^{-1}$ .

Show solutionHide solution

Series. The truncated exponential $\sum_{k=0}^{n}(-1)^k/k!\to e^{-1}$ .

Conclusion. $D_n/n!\to1/e\approx0.3679$ .

Interpretation. For large $n$ , the probability that a random permutation is a derangement approaches $1/e$ .