Editing Derangement
You are currently browsing as guest..
To change this, fill in the following fields:
Username
Password
Click here to reset your password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Thu Apr 18 14:43:41 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