Difference between revisions of "Derangement"
m |
|||
Line 2: | Line 2: | ||
==Notation== | ==Notation== | ||
− | 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>. (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 is given by the formula | + | 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 |
+ | |||
+ | \[ | ||
+ | !n = n \cdot !(n - 1) + (-1)^n | ||
+ | \] | ||
+ | |||
+ | and | ||
+ | |||
+ | \[ | ||
+ | !n = (n - 1)(!(n - 1) + !(n - 2)) | ||
+ | \] | ||
+ | |||
+ | and is given by the formula | ||
<cmath>!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.</cmath> | <cmath>!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.</cmath> |
Revision as of 22:43, 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
[hide]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.