Derangements

We use the Principle of Inclusion-Exclusion (Principle of Inclusion-Exclusion).

Setup. Work inside the universe $S_n$ of all $n!$ permutations of $[n]$. For each $i \in [n]$, let

be the set of permutations fixing $i$. A permutation is a derangement exactly when it lies in none of the $A_i$, so

Computing intersections. Fix a subset $T \subseteq [n]$ with $|T| = k$. We claim

Indeed, a permutation lying in $\bigcap_{i\in T} A_i$ must satisfy $\sigma(i) = i$ for every $i \in T$; on the remaining $n - k$ elements of $[n]\setminus T$, $\sigma$ may act as any bijection of that set to itself (this does not disturb the fixed points in $T$, since $\sigma$ restricted to $[n]\setminus T$ is a bijection $[n]\setminus T \to [n]\setminus T$ — it must map into $[n]\setminus T$ because every point of $T$ is already used as an image by the identity on $T$, and $\sigma$ is a bijection of the whole set $[n]$). There are exactly $(n-k)!$ such bijections, proving the claim.

Applying inclusion-exclusion. The Principle of Inclusion-Exclusion states that for events (subsets) $A_1,\dots,A_n$ of a finite universe,

Grouping the sum by $k = |T|$, there are $\binom{n}{k}$ subsets $T$ of size $k$, each contributing $\left|\bigcap_{i\in T}A_i\right| = (n-k)!$ by the claim above. Hence

Simplifying. Since $\binom{n}{k}(n-k)! = \dfrac{n!}{k!(n-k)!}(n-k)! = \dfrac{n!}{k!}$, this becomes

Therefore

using $\frac{(-1)^0}{0!} = 1$ for the $k=0$ term. This is exactly the claimed formula. The case $n=0$ is handled by convention ($D_0 = 1 = 0!\cdot 1$), and the argument above is valid for every integer $n \ge 1$ since it used no property of $n$ beyond finiteness. $\blacksquare$

We give a direct combinatorial (bijective) proof, not relying on the closed formula above, so as to give an independent verification. Let $\sigma$ be a derangement of $[n]$. Consider the value $\sigma(n)$; since $\sigma$ is a derangement, $\sigma(n) = j$ for some $j \in \{1,\dots,n-1\}$ (that is, $j \ne n$), giving $n-1$ choices for $j$. Fix such a $j$. We split into two cases based on whether $\sigma(j) = n$.

Case A: $\sigma(j) = n$. Then $\sigma$ swaps $j$ and $n$. Removing both $j$ and $n$ from consideration, the restriction of $\sigma$ to $[n]\setminus\{j,n\}$ (a set of size $n-2$) is itself a bijection of that set to itself, and it must have no fixed points, because any fixed point there is a fixed point of $\sigma$. Conversely, given any derangement $\tau$ of the $(n-2)$-element set $[n]\setminus\{j,n\}$, we get a derangement $\sigma$ of $[n]$ by setting $\sigma(n) = j$, $\sigma(j) = n$, and $\sigma = \tau$ elsewhere. This is a bijection between such $\sigma$ and derangements of an $(n-2)$-set, so there are exactly $D_{n-2}$ permutations $\sigma$ in Case A (for this fixed $j$).

Case B: $\sigma(j) \neq n$. Define $\tau$ on $[n]\setminus\{n\}$ (an $(n-1)$-element set) by

This is well-defined as a map $[n]\setminus\{n\} \to [n]\setminus\{n\}$: for $i \ne j$, $\sigma(i) \ne n$ would need checking — indeed $\sigma(i) = n$ is impossible unless $i=j$ since $\sigma(n) = j \ne n$ means $n$'s preimage is $j$ (as $\sigma$ is a bijection, the unique preimage of $n$ under $\sigma$ is $j$). So for $i \ne j$, $\sigma(i) \ne n$, hence $\tau(i) = \sigma(i) \in [n]\setminus\{n\}$ automatically excludes $n$; and we also need $\tau(i) \ne i$ for $i \ne j$: this holds because $\sigma(i) \ne i$ (as $\sigma$ is a derangement). Also $\tau(j) = n \ne j$. So $\tau$ is a derangement of the $(n-1)$-set $[n]\setminus\{n\}$. This construction is reversible: given a derangement $\tau$ of $[n]\setminus\{n\}$ and a value $j = \tau^{-1}(n)$, we recover $\sigma$ by $\sigma(n) = j$, $\sigma(j) = \tau(j) = n$... Let us restate the reverse map cleanly: given any derangement $\tau$ of $[n-1]$-sized set $[n]\setminus\{n\}$ (which necessarily has $\tau(j) = n$ for no $i$, since $\tau$ maps into $[n]\setminus\{n\}$ — rather $\tau$ is a derangement of that set meaning $\tau(i)\ne i$, values ranging over $[n]\setminus\{n\}$ too, so $\tau$ never outputs $n$). To invert Case B's construction: given $\tau$, a derangement of $[n]\setminus\{n\}$, and given the chosen $j$, define $\sigma(n)=j$, $\sigma(j) = n$, and $\sigma(i) = \tau(i)$ for $i \notin \{j,n\}$. One checks $\sigma$ is a derangement of $[n]$: $\sigma(n) = j \ne n$; $\sigma(j) = n \ne j$; for $i \ne j,n$, $\sigma(i) = \tau(i) \ne i$ since $\tau$ is a derangement. This $\sigma$ satisfies $\sigma(j) = n \ne n$'s original role... more precisely this exactly matches "Case B" since here $\sigma(j) = n$, wait — that contradicts Case B's defining condition $\sigma(j) \ne n$. Let us redo this cleanly with correct case bookkeeping. Fix $j = \sigma(n)$. Case B is $\sigma(j) \ne n$. Define $\tau: [n]\setminus\{n\} \to [n]\setminus\{n\}$ by $\tau(i) = \sigma(i)$ for $i \ne j$, and $\tau(j) = n$ is not used; instead set $\tau(j) := \sigma(j)$ is wrong since $\sigma(j)\in[n]\setminus\{n\}$ already (as $\sigma(j)\ne n$ in Case B) — so actually $\sigma$ restricted to $[n]\setminus\{n\}$ almost works as a map to $[n]\setminus\{n\}$ except that the value $j$ receives image $n$ from the "missing" element $n$, i.e. $\sigma(n) = j$ tells us $j$'s preimage is $n$, not that $\sigma$ maps $j$ somewhere disallowed. The correct fix-up is: define $\tau:[n]\setminus\{n\}\to[n]\setminus\{n\}$ by $\tau(i)=\sigma(i)$ for all $i \ne n$, except redefine nothing — we must handle that $\sigma(j)$ could equal anything in $[n]\setminus\{n,j\}$ (Case B excludes $\sigma(j)=n$, and $\sigma(j) \ne j$ always). Since $\sigma$ maps $[n]\setminus\{n\}$ bijectively onto $[n]\setminus\{j\}$ (because $\sigma(n)=j$ is the unique preimage of $j$), the map $\sigma|_{[n]\setminus\{n\}}$ is not a self-map of $[n]\setminus\{n\}$ — its image misses $j$ and includes $n$ instead (from $i=j$, only if $\sigma(j)=n$, excluded in Case B) — actually since $\sigma(j)\ne n$ in Case B, and $\sigma(n)=j$, the image of $\sigma|_{[n]\setminus\{n\}}$ is $[n]\setminus\{j\}$, which still doesn't include $n$'s slot correctly. To fix this, define $\tau$ on $[n]\setminus\{n\}$ by: $\tau(i)=\sigma(i)$ for $i\ne j$, and $\tau(j) = n$... but $n \notin [n]\setminus\{n\}$. We resolve this the standard way: relabel $n$ as $j$ within the image. Define $\tau: [n]\setminus\{n\} \to [n]\setminus\{n\}$ by

The clean, standard construction is: define $\tau$ by merging the roles of $n$ and $j$. Since $\sigma(n) = j$ and $\sigma(j) \ne n$ (Case B), define

This $\tau$ is a self-map of $[n]\setminus\{n\}$: for $i \ne j$ ($i\ne n$), $\sigma(i)$ never equals $n$ (its only preimage is $n$ itself, not $i$), so $\sigma(i) \in [n]\setminus\{n\}$; and $\tau(j)=\sigma(j) \in [n]\setminus\{n\}$ by Case B's hypothesis $\sigma(j)\ne n$ together with $\sigma(j) \ne j$ automatically. Injectivity of $\tau$ on $[n]\setminus\{n\}$ follows from injectivity of $\sigma$ on $[n]$ restricted to this domain (the only collision risk, values equal to $n$, cannot occur as just shown). Also $\tau(i) \ne i$ for all $i$ in the domain: for $i \ne j$, $\tau(i) = \sigma(i) \ne i$ since $\sigma$ is a derangement; for $i=j$, $\tau(j) = \sigma(j) \ne j$, again since $\sigma$ is a derangement. So $\tau$ is a derangement of the $(n-1)$-set $[n]\setminus\{n\}$. This construction $\sigma \mapsto (\tau, j)$ is invertible: given a derangement $\tau$ of $[n]\setminus\{n\}$ and a chosen $j \in [n]\setminus\{n\}$, define $\sigma(n) = j$, $\sigma(j) = \tau(j)$, and $\sigma(i)=\tau(i)$ for $i \ne j,n$. Then $\sigma$ is a permutation of $[n]$ (bijectivity checks directly), it is a derangement (same checks as above, reversed), $\sigma(n)=j\ne n$, and $\sigma(j)=\tau(j)\ne n$ automatically since $\tau$ takes values in $[n]\setminus\{n\}$ — so this lands exactly in Case B. Hence Case B permutations $\sigma$ (for fixed $j$) are in bijection with derangements $\tau$ of an $(n-1)$-element set, giving $D_{n-1}$ of them.

Total count. For each of the $n-1$ choices of $j = \sigma(n)$, there are $D_{n-2}$ derangements of type Case A and $D_{n-1}$ of type Case B, and every derangement falls into exactly one case for its own value of $j$. Summing,

By induction on $n$, using the closed formula $D_n = n!\sum_{k=0}^n (-1)^k/k!$ (proved above; this is a direct algebraic manipulation, not a circular reuse of the recurrence itself). Compute:

Then

using $(-1)^n = n!\cdot\frac{(-1)^n}{n!}$ for the middle step. The base case $n=1$: $1\cdot D_0 + (-1)^1 = 1 - 1 = 0 = D_1$ (indeed the only permutation of $\{1\}$ is the identity, which fixes $1$, so $D_1=0$), confirming consistency. $\blacksquare$

Part 1: the limit. By the counting formula,

This is precisely the $n$-th partial sum of the Taylor series

which converges absolutely (by the ratio test: $\left|\frac{(-1)^{k+1}/(k+1)!}{(-1)^k/k!}\right| = \frac{1}{k+1} \to 0 < 1$) to $e^{-1}$, since the exponential function $e^x = \sum_{k\ge 0} x^k/k!$ has infinite radius of convergence and this is its value at $x=-1$. Absolute (indeed unconditional) convergence of the series to $e^{-1}$ means exactly that the sequence of partial sums $p_n$ converges to $e^{-1}$:

Part 2: nearest integer. We must show $|D_n - n!/e| < 1/2$ for all $n \ge 1$, which implies $D_n$ is the unique nearest integer to $n!/e$ (note $n!/e$ is irrational for every $n\ge 1$ since $e$ is irrational and $n!$ is a nonzero rational integer, so there is never a tie at exactly $1/2$). The tail of the alternating series for $e^{-1}$ satisfies, by the alternating series remainder bound (valid since $1/k!$ is decreasing to $0$),

(This is the standard alternating series estimate: for a series $\sum (-1)^k a_k$ with $a_k \downarrow 0$, the error after truncating at term $k=n$ is bounded by the first omitted term $a_{n+1}$; here $a_{n+1} = \frac{1}{(n+1)!}$.) Multiplying through by $n!$:

For $n \ge 1$, $\frac{1}{n+1} \le \frac{1}{2}$, with equality only if $n=1$. We must check $n=1$ separately since the bound alone gives $\le 1/2$, not strictly less. Direct computation: $D_1 = 0$ and $1!/e = 1/e \approx 0.3679$, so $|1!/e - D_1| \approx 0.3679 < 0.5$. For $n \ge 2$, $\frac{1}{n+1} \le \frac13 < \frac12$ strictly, so the bound already gives strict inequality $|n!/e - D_n| < 1/2$. Hence for every $n \ge 1$, $|n!/e - D_n| < 1/2$, so $D_n$ is the unique integer within distance $1/2$ of $n!/e$, i.e. the nearest integer: