Difference between revisions of "Derangement"
m |
|||
Line 4: | Line 4: | ||
The number of derangements of an <math>n</math>-element set is called the <math>n</math>th derangement number or the ''subfactorial'' of <math>n</math> and is sometimes denoted <math>!n</math> or <math>D_n</math>. (Note that using this notation may require some care, as <math>a!b</math> can potentially mean both <math>(a!)b</math> and <math>a(!b)</math>.) This number satisfies the recurrences | The number of derangements of an <math>n</math>-element set is called the <math>n</math>th derangement number or the ''subfactorial'' of <math>n</math> and is sometimes denoted <math>!n</math> or <math>D_n</math>. (Note that using this notation may require some care, as <math>a!b</math> can potentially mean both <math>(a!)b</math> and <math>a(!b)</math>.) This number satisfies the recurrences | ||
− | + | <cmath> | |
!n = n \cdot !(n - 1) + (-1)^n | !n = n \cdot !(n - 1) + (-1)^n | ||
− | + | </cmath> | |
and | and | ||
− | + | <cmath> | |
− | !n = (n - 1)(!(n - 1) + !(n - 2)) | + | !n = (n - 1)\cdot (!(n - 1) + !(n - 2)) |
− | + | </cmath> | |
and is given by the formula | and is given by the formula |
Revision as of 23:44, 10 January 2008
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
and
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.