Editing Derangement
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Fri Apr 19 11:03:32 2024.
Press
to finish editing.
Who can edit this page?
World editing disabled
Members
Council
Admin
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 * EQN:d_n=n!\sum_{i=0}^n\frac{(-1)^i}{i!} For example: * EQN: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. [[[>50 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: * EQN:{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 EQN:d_n. As */n/* gets larger the probability that a randomly chosen permutation is a derangement approaches * EQN:\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!) ---- * http://en.wikipedia.org/wiki/Derangement * http://mathworld.wolfram.com/Derangement.html