Difference between revisions of "Derangement"

m (minor)
Line 1: Line 1:
A '''derangement''' is a [[permutation]] with no [[fixed point]]s.  That is, a derangement leaves nothing 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>.   
+
A '''derangement''' is a [[permutation]] with no [[fixed point]]s.  That is, a derangement of a [[set]] leaves no [[element]]s in their original places.  For example, the derangements of <math>\{1,2,3\}</math> are <math>\{2, 3, 1\}</math> and <math>\{3, 1, 2\}</math>.   
  
The number of derangements of a [[set]] of <math>n</math> objects is sometimes denoted <math>!n</math> and is given by the formula:
+
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:
  
<math>\displaystyle !n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}</math>
+
<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-[[element]] set is <math>3! \cdot \sum_{k = 0}^3 \frac{(-1)^k}{k!} = 6\cdot(\frac{1}{1} - \frac{1}{1} + \frac{1}{2} - \frac{1}{6}) = 2</math>, which we know to be correct.
+
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 ==
 +
*[[Correspondence]]
  
 
{{stub}}
 
{{stub}}

Revision as of 19:11, 15 May 2007

A derangement is a permutation with no fixed points. That is, a derangement of a set leaves no elements in their original places. For example, the derangements of $\{1,2,3\}$ are $\{2, 3, 1\}$ and $\{3, 1, 2\}$.

The number of derangements of a set of $n$ objects is sometimes denoted $\displaystyle !n$ and is given by the formula:

$\displaystyle !n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$

Thus, the number derangements of a 3-element set is $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$, which we know to be correct.

See also

This article is a stub. Help us out by expanding it.