Difference between revisions of "Derangement"
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]] 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. | 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 and formula== |
| − | 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 ''rencontres 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> | <cmath> | ||
| Line 18: | Line 18: | ||
<cmath>!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.</cmath> | <cmath>!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.</cmath> | ||
| − | + | For example, 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. | |
| + | |||
| + | The first few derangements, starting from <math>n=0</math>, are <math>1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, \ldots.</math> | ||
| + | |||
| + | ==Limit as n approaches ∞== | ||
| + | |||
| + | From the recurrence <math>!n=n\cdot!(n-1)+(-1)^{n}</math>, we can find that <math>\lim_{n\to\infty}\frac{!n}{n!} =\frac{1}{e} \approx 0.3679\ldots.</math> | ||
| + | |||
| + | Also, <math>!n = \left\lfloor\frac{n!}{e}+\frac{1}{2}\right\rfloor.</math> | ||
==Problems== | ==Problems== | ||
Revision as of 17:15, 13 February 2009
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.
Notation and formula
The number of derangements of an 
-element set is called the th derangement number or rencontres 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)
For example, the number derangements of a 3-element set is 
, which we know to be correct.
The first few derangements, starting from 
, are 
Limit as n approaches ∞
From the recurrence 
, we can find that 
Also, 
Problems
Introductory
See also
This article is a stub. Help us out by expanding it.
