Difference between revisions of "Derangement"
m |
(category) |
||
| Line 1: | Line 1: | ||
| − | 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. | + | A '''derangement''' (or a '''subfactorial''') 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. |
| + | ==Notation== | ||
| + | Because a derangement is a subset of a permutation, which can be found using the factorial, it is notated <math>!n</math>. This sometimes confuses students, as they don't know whether <math>a!b</math> means <math>(a!)b</math> or <math>a(!b)</math>. | ||
| + | |||
| + | ==Formula== | ||
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>!n</math> and is given by the formula | ||
| − | < | + | <cmath>!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}</cmath> |
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. | 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. | ||
| − | == Introductory == | + | ==Problems== |
| + | === Introductory === | ||
* [[University_of_South_Carolina_High_School_Math_Contest/1993_Exam/Problem_11 | 1993 University of South Carolina Math Contest Problem 11]] | * [[University_of_South_Carolina_High_School_Math_Contest/1993_Exam/Problem_11 | 1993 University of South Carolina Math Contest Problem 11]] | ||
* [[2005_PMWC_Problems/Problem_I11 | 2005 PMWC Problem I11]] | * [[2005_PMWC_Problems/Problem_I11 | 2005 PMWC Problem I11]] | ||
| Line 15: | Line 20: | ||
{{stub}} | {{stub}} | ||
| + | [[Category:Combinatorics]] | ||
Revision as of 22:09, 10 January 2008
A derangement (or a subfactorial) 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.
Notation
Because a derangement is a subset of a permutation, which can be found using the factorial, it is notated 
. This sometimes confuses students, as they don't know whether 
means 
or 
.
Formula
The number of derangements of a set of 
objects is sometimes denoted and is given by the formula
![\[!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}\]](http://latex.artofproblemsolving.com/c/3/a/c3adbbb412cbd1bb11b75b77598c33f0e679479a.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.
