Difference between revisions of "Derangement"
Mysmartmouth (talk | contribs) |
(Undo revision 215857 by Marianasinta (talk)) (Tag: Undo) |
||
(15 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
− | A '''derangement''' is a [[permutation]] with no [[fixed point]]s. | + | 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 and formula== | ||
+ | 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> | ||
+ | !n = n \cdot !(n - 1) + (-1)^n | ||
+ | </cmath> | ||
− | + | and | |
+ | <cmath> | ||
+ | !n = (n - 1)\cdot (!(n - 1) + !(n - 2)) | ||
+ | </cmath> | ||
+ | and is given by the formula | ||
+ | |||
+ | <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> | ||
+ | |||
+ | ==Proof of Formula== | ||
+ | This can be proven using PIE. First, you take <math>n!</math>, which represents all arrangements of the whole sequence. Then, you must subtract all arrangements in which each element appears in its original location, and now you have <math>n!-\binom{n}{1}(n-1)!</math>. Then, you must add back in permutations in which each set of two elements stay in their original positions, as we subtracted them twice. Now, we have <math>n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!</math>. PIE continues to give us this pattern. We have to alternate between subtracting and adding. | ||
+ | |||
+ | Now, we can change the form of <math>\binom{n}{k}(n-k)!</math>. This is written as <math>\frac{n!}{k!(n-k)!}\times(n-k)!=\frac{n!}{k!}</math>. We can now write our relation as <math>n!-\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+...+(-1)^n(\frac{n!}{n!})</math>. We can factor out <math>n!</math> and get <math>n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!})=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}</math>. | ||
+ | |||
+ | ==Limit as n approaches <math>\infty</math>== | ||
+ | |||
+ | 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== | ||
+ | === Introductory === | ||
+ | * [[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]] | ||
+ | |||
+ | == See also == | ||
+ | *[[Correspondence]] | ||
{{stub}} | {{stub}} | ||
+ | [[Category:Combinatorics]] |
Latest revision as of 12:57, 20 February 2024
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
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
Proof of Formula
This can be proven using PIE. First, you take , which represents all arrangements of the whole sequence. Then, you must subtract all arrangements in which each element appears in its original location, and now you have
. Then, you must add back in permutations in which each set of two elements stay in their original positions, as we subtracted them twice. Now, we have
. PIE continues to give us this pattern. We have to alternate between subtracting and adding.
Now, we can change the form of . This is written as
. We can now write our relation as
. We can factor out
and get
.
Limit as n approaches ![$\infty$](//latex.artofproblemsolving.com/b/6/7/b671f1bb7e4ee86584347d5d22f1dc8abdb5bef2.png)
From the recurrence , we can find that
Also,
Problems
Introductory
See also
This article is a stub. Help us out by expanding it.