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 16: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.
Contents
[hide]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
and
and is given by the formula
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.