Derangement

A derangement (or a subfactorial) 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 not $\{3,2, 1\}$ because 2 is a fixed point.

Notation

Because a derangement is a subset of a permutation, which can be found using the factorial, it is notated $!n$ . This sometimes confuses students, as they don't know whether $a!b$ means $(a!)b$ or $a(!b)$ .

Formula

The number of derangements of a set of $n$ objects is sometimes denoted $!n$ 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.

Page

Toolbox

Search

Derangement

Contents

Notation

Formula

Problems

Introductory

See also