Derangement

Revision as of 22:44, 10 January 2008 by JBL (talk | contribs)

A derangement is a permutation with no fixed points. That is, a derangement of a set leaves no element in its original place. For example, the derangements of $\{1,2,3\}$ are $\{2, 3, 1\}$ and $\{3, 1, 2\}$, but $\{3,2, 1\}$ is not a derangement of $\{1,2,3\}$ because 2 is a fixed point.

Notation

The number of derangements of an $n$-element set is called the $n$th derangement number or the subfactorial of $n$ and is sometimes denoted $!n$ or $D_n$. (Note that using this notation may require some care, as $a!b$ can potentially mean both $(a!)b$ and $a(!b)$.) This number satisfies the recurrences

\[!n = n \cdot !(n - 1) + (-1)^n\]

and

\[!n = (n - 1)\cdot (!(n - 1) + !(n - 2))\]

and is given by the formula

\[!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.\]

Thus, the number derangements of a 3-element set is $3! \cdot \sum_{k = 0}^3 \frac{(-1)^k}{k!} = 6\cdot\left(\frac{1}{1} - \frac{1}{1} + \frac{1}{2} - \frac{1}{6}\right) = 2$, which we know to be correct.

Problems

Introductory

See also

This article is a stub. Help us out by expanding it.