20
$\begingroup$

I am trying to figure out how many permutations exist in a set where none of the numbers equal their own position in the set; for example, $3,1,5,2,4$ is an acceptable permutation where $3,1,2,4,5$ is not because 5 is in position 5. I know that the number of total permutations is $n!$.
Is there a formula for how many are acceptable given the case that no position holds its own number?

$\endgroup$
19
$\begingroup$

What you are looking for is known as derangement. However, for counting the number of derangement for say $n$-elements you could possible use a trick, compute$\frac{n!}{e}$ and then round off to an integer and this will give you the desired result.

This is actually another application of $e$, which was discovered by Jacob Bernoulli in the problem of derangement, also known as the hat check problem.

$\endgroup$
12
$\begingroup$

Check out http://en.wikipedia.org/wiki/Derangement

$\endgroup$
  • 3
    $\begingroup$ Please add more content from the cited page (e.g. describe derangements, etc). Otherwise, this should really be left as a comment. $\endgroup$ – robjohn Aug 7 '14 at 0:07
3
$\begingroup$

In his combinatorics lecture notes, Jacob Lurie analyses the problem of derangements. It is at the end of these note: http://www.math.harvard.edu/~lurie/155notes/lecture3.pdf

and continues into these

http://www.math.harvard.edu/~lurie/155notes/lecture4.pdf.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy