Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Derangement"

m
(Undo revision 215857 by Marianasinta (talk))
(Tag: Undo)
 
(11 intermediate revisions by 7 users not shown)
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''' 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.
  
−
The number of derangements of a set of <math>n</math> objects is sometimes denoted <math>!n</math> and is given by the formula
+
==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
  
−
<div style="text-align:center;"><math>!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}</math></div>
+
<cmath>
 +
!n = n \cdot !(n - 1) + (-1)^n
 +
</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.
+
and
  
−
== Introductory ==
+
<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]]
 
* [[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 42:
  
 
{{stub}}
 
{{stub}}
 +
[[Category:Combinatorics]]

Latest revision as of 11: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 $\{1,2,3\}$ are $\{2, 3, 1\}$ and $\{3, 1, 2\}$, but $\{3,2, 1\}$ is not a derangement of $\{1,2,3\}$ because 2 is a fixed point.

Notation and formula

The number of derangements of an $n$-element set is called the $n$th derangement number or rencontres number, or the subfactorial of $n$ and is sometimes denoted $!n$ or $D_n$. (Note that using this notation may require some care, as $a!b$ can potentially mean both $(a!)b$ and $a(!b)$.) This number satisfies the recurrences

\[!n = n \cdot !(n - 1) + (-1)^n\]

and

\[!n = (n - 1)\cdot (!(n - 1) + !(n - 2))\]

and is given by the formula

\[!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.\]

For example, 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.

The first few derangements, starting from $n=0$, are $1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, \ldots.$

Proof of Formula

This can be proven using PIE. First, you take $n!$, 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 $n!-\binom{n}{1}(n-1)!$. 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 $n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!$. PIE continues to give us this pattern. We have to alternate between subtracting and adding.

Now, we can change the form of $\binom{n}{k}(n-k)!$. This is written as $\frac{n!}{k!(n-k)!}\times(n-k)!=\frac{n!}{k!}$. We can now write our relation as $n!-\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+...+(-1)^n(\frac{n!}{n!})$. We can factor out $n!$ and get $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!}$.

Limit as n approaches $\infty$

From the recurrence $!n=n\cdot!(n-1)+(-1)^{n}$, we can find that $\lim_{n\to\infty}\frac{!n}{n!} =\frac{1}{e} \approx 0.3679\ldots.$

Also, $!n = \left\lfloor\frac{n!}{e}+\frac{1}{2}\right\rfloor.$

Problems

Introductory

See also

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Derangement&oldid=215910"