Difference between revisions of "Derangement"
m |
|||
| Line 1: | Line 1: | ||
| − | A '''derangement''' | + | A '''derangement''' is a [[permutation]] with no [[fixed point]]s. That is, a derangement of a [[set]] leaves no [[element]] in its original place. For example, the derangements of <math>\{1,2,3\}</math> are <math>\{2, 3, 1\}</math> and <math>\{3, 1, 2\}</math>, but <math>\{3,2, 1\}</math> is not a derangement of <math>\{1,2,3\}</math> because 2 is a fixed point. |
==Notation== | ==Notation== | ||
Revision as of 22:38, 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 
. (Note that using this notation may require some care, as 
can potentially mean both 
and 
.) This number 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.
