Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
Check out en.wikipedia.org/wiki/Derangement –  Florian Dec 17 '10 at 13:13
    
Florian, your comment should be an answer. –  Anthony Labarre Dec 17 '10 at 13:15
1  
This recent math.SE question asks for a proof of one of the formulas for the number of derangements: math.stackexchange.com/questions/14477. –  Mike Spivey Dec 17 '10 at 15:52

3 Answers 3

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.