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 22: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
![\[!n = n \cdot !(n - 1) + (-1)^n\]](http://latex.artofproblemsolving.com/7/7/b/77bbc2c06218239b21273269fae4f49949611b9b.png)
and
![\[!n = (n - 1)\cdot (!(n - 1) + !(n - 2))\]](http://latex.artofproblemsolving.com/a/4/7/a47f5599c71b6cd229e2892334e2e2a67e996920.png)
and is given by the formula
![\[!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.\]](http://latex.artofproblemsolving.com/a/6/d/a6dc5b03b0f0635ae5384b8a78967ac7ae367890.png)
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.
