Derangements and 1/e

Return $n$ checked hats at random. The probability that nobody receives their own hat tends, as $n$ grows, to $1/e = 0.367879\ldots$ — and the convergence is so fast that the limit is visible at a dinner party.1

1

The problem is Montmort’s jeu de rencontre (1708); the count $D_n$ is the number of derangements — permutations without fixed points.

Inclusion–exclusion over which hats are fixed gives

$$D_n \;=\; n!\sum_{k=0}^{n}\frac{(-1)^k}{k!},\qquad \frac{D_n}{n!}\;\longrightarrow\;\frac1e.$$

The sum is a truncation of the series for $e^{-1}$, and because that series alternates with shrinking terms,

$$\Bigl|\,D_n-\frac{n!}{e}\,\Bigr| \;<\; \frac{1}{n+1} \;\le\; \frac12 \quad (n\ge1),$$

so the count of derangements is simply $n!/e$ rounded to the nearest integer. An exact combinatorial quantity, recovered by rounding a transcendental number: this is the identity that makes $e$ feel inevitable rather than invented.

The recurrence

Element $n$ must map somewhere, say to $j$. Either $j$ maps straight back — a 2-cycle, leaving $D_{n-2}$ ways — or it does not, which is equivalent to deranging $n-1$ items. With $n-1$ choices of $j$,

$$D_n \;=\; (n-1)\bigl(D_{n-1}+D_{n-2}\bigr),\qquad D_1 = 0,\ D_2 = 1.$$

Already $D_9 = 133496$ against $9! = 362880$ gives $0.367879\ldots$ — six correct decimals of $1/e$ from a fact about nine hats. The catalog places $e = 2.718\ldots$ at ℵ2718 accordingly.