Numbers and Sets | Part IA, 2006

State and prove the Inclusion-Exclusion Principle.

A permutation σ\sigma of {1,2,,n}\{1,2, \ldots, n\} is called a derangement if σ(j)j\sigma(j) \neq j for every jnj \leqslant n. Use the Inclusion-Exclusion Principle to find a formula for the number f(n)f(n) of derangements of {1,2,,n}\{1,2, \ldots, n\}. Show also that f(n)/nf(n) / n ! converges to 1/e1 / e as nn \rightarrow \infty.

Typos? Please submit corrections to this page on GitHub.