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"

(category)
Line 1: Line 1:
−
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.
+
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 <math>\{3,2, 1\}</math> is not a derangement of <math>\{1,2,3\}</math> because 2 is a fixed point.
  
 
==Notation==
 
==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>.
+
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>. (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 is given by the formula
  
−
==Formula==
+
<cmath>!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.</cmath>
−
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.

Revision as of 23:38, 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 $\{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

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

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

Thus, 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.

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=22311"