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