Derangement

From AoPSWiki

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.

Personal tools

Navigation

Search

Toolbox

Derangement

From AoPSWiki

Contents

Notation

Problems

Introductory

See also