Problem
COM-B2-M02-P009 Derangement Formula
#9
★★★☆☆ Level 3 of 5
Prove that the number of permutations of \(n\) elements with no fixed points is \(D_n=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}\).
Let \(A_i\) be the event “element \(i\) is fixed”.
If \(i\) elements are chosen to be fixed, the remaining \(n-i\) elements can be permuted in \((n-i)!\) ways. By inclusion-exclusion,
\[D_n=\sum_{i=0}^n(-1)^i\binom ni(n-i)!=n!\sum_{i=0}^n\frac{(-1)^i}{i!}.\]
The key formula of the module.