Derangement

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

$d_n=n!\sum_{i=0}^n\frac{(-1)^i}{i!}$

For example:

$d_{5}=5!$\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}$$ (which is 44)

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:

${n\choose~0}d_0+{n\choose~1}d_1+{n\choose~2}d_2+\ldots+{n\choose~n}d_n=n!$

This gives a recursive formula for computing $d_n.$

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

$\lim_{n\to\infty}\frac{d_n}{n!}=e^{\small{-1}}\approx~0.368\dots$

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

Last change to this page
Full Page history
Links to this page

Edit this page
(with sufficient authority)
Change password

Recent changes
All pages
Search

Derangement

Navigation