Derangement

Number of possible permutations and derangements of n elements. n! (n factorial) is the number of n-permutations; !n (n subfactorial) is the number of derangements – n-permutations where all of the n elements change their initial places.

In combinatorial mathematics, a derangement is a permutation of the elements of a set in which no element appears in its original position. In other words, a derangement is a permutation that has no fixed points.

The number of derangements of a set of size n is known as the subfactorial of n or the n-th derangement number or n-th de Montmort number (after Pierre Remond de Montmort). Notations for subfactorials in common use include !n, Dn, dn, or n¡.[1][2]

For n > 0, the subfactorial !n equals the nearest integer to n!/e, where n! denotes the factorial of n and e is Euler's number.[3]

The problem of counting derangements was first considered by Pierre Raymond de Montmort in his Essay d'analyse sur les jeux de hazard.[4] in 1708; he solved it in 1713, as did Nicholas Bernoulli at about the same time.

  1. ^ The name "subfactorial" originates with William Allen Whitworth; see Cajori, Florian (2011), A History of Mathematical Notations: Two Volumes in One, Cosimo, Inc., p. 77, ISBN 9781616405717.
  2. ^ Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics (1994), Addison–Wesley, Reading MA. ISBN 0-201-55802-5
  3. ^ Cite error: The named reference Hassani2003 was invoked but never defined (see the help page).
  4. ^ de Montmort, P. R. (1708). Essay d'analyse sur les jeux de hazard. Paris: Jacque Quillau. Seconde Edition, Revue & augmentée de plusieurs Lettres. Paris: Jacque Quillau. 1713.