Statistics How To

Derangements: Definition

Permutations >

Derangements are permutations in which no object is returned to its original, right, or natural place. They are sometimes called complete permutations or rencontres numbers.

Another way of saying this is that a derangement is a permutation without fixed points. π(i) ≠ i for every i being permutated, where:

  • π is the permutation,
  • i is the objects being acted upon.

Note: Pi is fairly standard notation for permutations; any Greek letter is fair game, but in general pi is the one chosen across the board.

  • There is no derangement possible for a set with one element; The set {a} cannot be written any other way.
  • A set with two elements has just one derangement. For example, the derangement of {a, b} is {b, a}.
  • For a set with three elements, there are two possible derangements. (If your set is {a, b, c}, then {b, c, a} and {c, a, b} are the two possibilities.

Formula

The number of permutations of a set of n elements is given by n! (n factorial, or n · (n-1) · (n-2)…(1)). The number of derangements of a set of n elements, which we write Dn, is given by

This looks long and complicated, but a little calculus can reduce it to an equation that is very, very easy to use:


Where:

  • The square bracket, [ ], is the ‘nearest integer function’, a function which rounds whatever is inside the brackets to the nearest integer.
  • “e” is Euler’s number.

The number of derangements is sometimes also written as !n, and then is called the subfactorial.

Examples of Derangements Problems

The formula above allows us to solve more involved questions like, “Six students placed their phones in one bag and then all grabbed one out randomly. What is the likelihood that no one would get his own phone?”

The number of possible permutations in this case is 6!, or 6 · 5 · 4 · 3 · 2 · 1= 720. The number of possible derangements is [6!/e], or 265. So the probability that no one would get their own phone is 265/720, or 36 percent.

References

Cameron, Peter. Lectures on Derangements
retrieved from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.421.2852&rep=rep1&type=pdf on Feb 6, 2018

Arrangements and Derangements
retrieved from http://www.mathcs.emory.edu/~rg/derangements.pdf on Feb 6, 2018

Martinez, Panholzer, and Prodinger. Creating Random Derangements
retrieved from https://www.cs.upc.edu/~conrado/research/talks/analco08.pdf on Feb 10, 2018

Weisstein, Eric W. Derangement. From MathWorld–A Wolfram Web Resource. retrieved from http://mathworld.wolfram.com/Derangement.html on Feb 10, 2018

------------------------------------------------------------------------------

If you prefer an online interactive environment to learn R and statistics, this free R Tutorial by Datacamp is a great way to get started. If you're are somewhat comfortable with R and are interested in going deeper into Statistics, try this Statistics with R track.

Comments are now closed for this post. Need help or want to post a correction? Please post a comment on our Facebook page and I'll do my best to help!
Derangements: Definition was last modified: March 27th, 2018 by HannahM