Difference between revisions of "Derangement"
m (minor) |
m |
||
| Line 1: | Line 1: | ||
| − | A '''derangement''' is a [[permutation]] with no [[fixed point]]s. That is, a derangement of a [[set]] leaves no [[element]] | + | 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 not <math>\{3,2, 1\}</math> because 2 is a fixed point. |
| − | The number of derangements of a | + | The number of derangements of a set of <math>n</math> objects is sometimes denoted <math>\displaystyle !n</math> and is given by the formula |
<div style="text-align:center;"><math>\displaystyle !n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}</math></div> | <div style="text-align:center;"><math>\displaystyle !n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}</math></div> | ||
| − | Thus, the number derangements of a 3- | + | Thus, the number derangements of a 3-element set is <math>3! \cdot \sum_{k = 0}^3 \frac{(-1)^k}{k!} = 6\cdot\left(\frac{1}{1} - \frac{1}{1} + \frac{1}{2} - \frac{1}{6}\right) = 2</math>, which we know to be correct. |
== See also == | == See also == | ||
Revision as of 10:37, 22 May 2007
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 not 
because 2 is a fixed point.
The number of derangements of a set of 
objects is sometimes denoted 
and is given by the formula
Thus, the number derangements of a 3-element set is 
, which we know to be correct.
See also
This article is a stub. Help us out by expanding it.
