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 are
and
, but
is not a derangement of
because 2 is a fixed point.
Contents
Notation
The number of derangements of an -element set is called the
th derangement number or the subfactorial of
and is sometimes denoted
or
. (Note that using this notation may require some care, as
can potentially mean both
and
.) This number satisfies the recurrences
\[ !n = n \cdot !(n - 1) + (-1)^n \]
and
\[ !n = (n - 1)(!(n - 1) + !(n - 2)) \]
and is given by the formula
Thus, the number derangements of a 3-element set is , which we know to be correct.
Problems
Introductory
See also
This article is a stub. Help us out by expanding it.