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 | + | 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== | ||
− | + | 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 | |
− | + | <cmath>!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.</cmath> | |
− | |||
− | |||
− | <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 22: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 are and , but is not a derangement of because 2 is a fixed point.
Contents
[hide]Notation
The number of derangements of an -element set is called the th derangement number or the subfactorial of and is sometimes denoted . (Note that using this notation may require some care, as can potentially mean both and .) This number is given by the formula
Thus, the number derangements of a 3-element set is , which we know to be correct.
Problems
Introductory
See also
This article is a stub. Help us out by expanding it.