Lesson 4

Theorem (Derangement problem). Let \(\pi\) be a random permutation of elements \([n]\). Then the probability that \(\pi\) has no fixed points (i.e. \(\pi(i) \neq i\) for all \(i \in [n]\)) tends to \(1/e\): \[\lim_{n \to \infty}\Pr_{\pi \gets S_n}[\pi(i) \neq i \text{ for all \(1 \le i \le n\)}]=\frac{1}{e} \ .\]

Proof. Denote by \(B_{i}\) the event “element \(i\) stayed in place”. Then the desired probability is \(1-\Pr[B_{1} \cup B_{2} \cup \dotsb \cup B_{n}]\). For the set \(I \subseteq [n]\), we have \(\Pr[\cap_{i \in I}B_{i}]=\frac{(n-|I|)!}{n!}\). Then by the inclusion-exclusion formula, we obtain that the required probability is: \[1-\sum_{\varnothing \neq I \subseteq \{1, 2, \dotsc, n\}}(-1)^{|I|+1}\cdot \frac{(n-|I|)!}{n!}=1-\sum_{i=1}^{n}(-1)^{i+1}\binom{n}{i}\frac{(n-i)!}{n!}=\sum_{i=0}^{n} \frac{(-1)^i}{i!}\ ,\] which is the initial part of the Taylor series for the function \(e^{x}\) at the point \(x=-1\) (\(e^{x}=\sum_{k=0}^{\infty}\frac{x^k}{k!}\)).◼