TOPICS
Search

Derangement


A derangement is a permutation in which none of the objects appear in their "natural" (i.e., ordered) place. For example, the only derangements of {1,2,3} are {2,3,1} and {3,1,2}, so !3=2. Similarly, the derangements of {1,2,3,4} are {2,1,4,3}, {2,3,4,1}, {2,4,1,3}, {3,1,4,2}, {3,4,1,2}, {3,4,2,1}, {4,1,2,3}, {4,3,1,2}, and {4,3,2,1}. Derangements are permutations without fixed points (i.e., having no cycles of length one). The derangements of a list of n elements can be computed in the Wolfram Language using

Derangements[l_List] := With[
  {perms = Permutations[l]},
  {supp = PermutationSupport /@ perms},
  Pick[perms, Length /@ supp, Length[l]]
]

The derangement problem was formulated by P. R. de Montmort in 1708, and solved by him in 1713 (de Montmort 1713-1714). Nicholas Bernoulli also solved the problem using the inclusion-exclusion principle (de Montmort 1713-1714, p. 301; Bhatnagar 1995, p. 8).

Derangements are also called rencontres numbers (named after rencontres solitaire) or complete permutations, and the number of derangements !n on n elements is called the subfactorial of n.

The function giving the number of distinct derangements on n elements is called the subfactorial !n and is equal to

!n=n!sum_(k=0)^(n)((-1)^k)/(k!)
(1)
=(Gamma(n+1,-1))/e
(2)

(Bhatnagar 1995, pp. 8-9), where Gamma(z,a) is the incomplete gamma function, or

 !n=[(n!)/e],
(3)

where k! is the usual factorial and [x] is the nearest integer function.

As the number of objects increases, the probability P that none appears in its correct position approaches

 P=lim_(n->infty)(!n)/(n!)=1/e
(4)

(Wells 1986, p. 27). In fact, the probability is very close to 1/e already even for as few as four points.

The number of derangements !n=d(n) of length n satisfy the recurrence relations

 d(n)=(n-1)[d(n-1)+d(n-2)]
(5)

and

 d(n)=nd(n-1)+(-1)^n,
(6)

with d(1)=0 and d(2)=1 (Skiena 1990, p. 33). The first few are 0, 1, 2, 9, 44, 265, 1854, ... (OEIS A000166). The recurrence can be solved exactly, although the sequence of d(n) cannot be expressed as a fixed number of hypergeometric terms (Petkovšek et al. 1996, pp. 157-160; Koepf 1998, p. 159).


See also

Married Couples Problem, Partial Derangement, Permutation, Root, Subfactorial

Explore with Wolfram|Alpha

References

Aitken, A. C. Determinants and Matrices. Westport, CT: Greenwood Pub., p. 135, 1983.Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 46-47, 1987.Bhatnagar, G. Inverse Relations, Generalized Bibasic Series, and their U(n) Extensions. Ph.D. thesis. Ohio State University, 1995.Comtet, L. "The 'Problème des Rencontres.' " §4.2 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 180-183, 1974.Coolidge, J. L. An Introduction to Mathematical Probability. Oxford, England: Oxford University Press, p. 24, 1925.Courant, R. and Robbins, H. What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 115-116, 1996.de Montmort, P. R. Essai d'analyse sur les jeux de hasard. Paris, 1708. Second edition published 1713-1714. Third edition reprinted in New York: Chelsea, pp. 131-138, 1980.Dickau, R. M. "Derangements." http://mathforum.org/advanced/robertd/derangements.html.Durell, C. V. and Robson, A. Advanced Algebra. London, p. 459, 1937.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Hassani, M. "Derangements and Applications." J. Integer Seq. 6, No. 03.1.2, 1-8, 2003. http://www.math.uwaterloo.ca/JIS/VOL6/Hassani/hassani5.html.Koepf, W. Hypergeometric Summation: An Algorithmic Approach to Summation and Special Function Identities. Braunschweig, Germany: Vieweg, 1998.Petkovšek, M.; Wilf, H. S.; and Zeilberger, D. A=B. Wellesley, MA: A K Peters, 1996. http://www.cis.upenn.edu/~wilf/AeqB.html.Roberts, F. S. Applied Combinatorics. Englewood Cliffs, NJ: Prentice-Hall, 1984.Ruskey, F. "Information on Derangements." http://www.theory.csc.uvic.ca/~cos/inf/perm/Derangements.html.Skiena, S. "Derangements." §1.4.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 33-34, 1990.Sloane, N. J. A. Sequence A000166/M1937 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. Enumerative Combinatorics, Vol. 1. New York: Cambridge University Press, p. 67, 1986.Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, p. 123, 1991.Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, p. 27, 1986.

Referenced on Wolfram|Alpha

Derangement

Cite this as:

Weisstein, Eric W. "Derangement." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Derangement.html

Subject classifications