Links to this page
Edit this page
Entry portal
Advice For New Users

A Derangement is a permutation that leaves nothing in its "natural" place. Alternatively, it's a function f from {1,...,n} to {1,...,n} such that f(i) is never i.

The number of derangements of n items is given by

For example:

The number of derangements of n objects is written !n and they are associated with combinations, permutations and factorials.
Colloquially, suppose 100 people are wearing hats, put them in a basket (yes, it's a very large basket) and then each pulls a hat out at random, then the probability that no one gets the right hat is about 37%

In particular, in any arrangement we can choose a selection of items to derange, then derange them, leaving the others unmoved. Hence:

This gives a recursive formula for computing $d_n.$

As n gets larger the probability that a randomly chosen permutation is a derangement approaches

This is also related to a Secret Santa problem (of which there are many!)

Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout