Derangement

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 not $\{3,2, 1\}$ because 2 is a fixed point.

The number of derangements of a set of $n$ objects is sometimes denoted $\displaystyle !n$ and is given by the formula

$\displaystyle !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

See also