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!)