Questions tagged [derangements]

A derangement of a set $S$ is a mapping $\sigma:S\to S$ such that $\sigma(x)\neq x$ for all $x\in S$ (or, more briefly, a permutation of $S$ with no fixed points). For example, the mapping $1\mapsto 2,\ 2\mapsto 3,\ 3\mapsto 1$ is a derangement of $\{1,2,3\}$, while $1\mapsto 1,\ 2\mapsto 3,\ 3\mapsto 2$ isn't (since $1$ remains fixed). $S$ may be infinite, but the finite case has been much better studied.

The number of derangements of an $n$-element set is commonly denoted as $!n$ or $D_n$, and called "$n$ subfactorial". In this example, we can easily see that $!3=2$.

There are various formulas for $!n$. By Inclusion-Exclusion, it is possible to prove that

\begin{equation}!n=\sum_{i=0}^n(-1)^i\cdot\frac{n!}{i!}.\tag{1}\label{1}\end{equation}

By then comparing this sum to the Taylor series of $e^x$, we can prove the surprising equality

\begin{equation}!n=\left[\frac{n!}e\right]\quad(n\geq1),\tag{2}\label{2}\end{equation}

where $[x]$ denotes the closest integer to $x$, and $e$ denotes Euler's number.

Other recursive formulas also exist. By a simple counting argument, we may prove

\begin{equation}!n=(n-1)(!(n-1)+!(n-2)).\tag{3}\label{3}\end{equation}

And by making use of $(\ref{1})$, we may also prove that

\begin{equation}!n=n(!(n-1))+(-1)^n.\tag{4}\label{4}\end{equation}