Possible Duplicate:
Number of permutations where n ≠ position n

I've got a HW problem for a Random Signals class I've got mostly figured out, but my approach would require a solution to another subproblem that I initially thought would be easy, but its not. It may well be that I am on the wrong track for the problem , but the subproblem is interesting enough in its own right that I'd like to figure it out.

The essence of the subproblem (not the actual HW problem) is:

How many different orderings of N objects are possible ensuring that no object is in its initial position?

My initial thinking was that the first one could move to any of (n-1) positions, then the 2nd could go to (n-2), etc. This would suggest (n-1)! orderings. However, this only works for n=2,and n=3, (1 and 2 "good" permutatations, respectively).

But when n>3 , there is a possibility of permutations within subsequences that increase the number.

With n=4, there are 9 good permutations: 2341 2413 2431 3421 3142 4123 4312 2143 4321 3412

6 of these 9 are made by permuting the entire sequence in a ring. The other 3 are from creating all possible subsequence arrangements of the 4 elements (where the length of the subsequence > 1) and permuting within the subsequence. i.e. in one arrangement, swap (1,2) and (3,4); in another arrangement, swap(1,4) and (2,3); in the 3rd swap (1,3), (2,4).

I've written a C++ program that uses next_permutation to calculate the number of good sequences. My hope was that I could see a pattern emerge. Nothing is coming to me ...

for n=2 there are 1 good permutations 
for n=3 there are 2 good permutations 
for n=4 there are 9 good permutations 
for n=5 there are 44 good permutations 
for n=6 there are 265 good permutations 
for n=7 there are 1854 good permutations 
for n=8 there are 14833 good permutations 
for n=9 there are 133496 good permutations 
for n=10 there are 1334961 good permutations 
for n=11 there are 14684570 good permutations 
for n=12 there are 176214841 good permutations 
for n=13 there are 2290792932 good permutations 

marked as duplicate by Listing, Quixotic, Srivatsan, J. M. is a poor mathematician, Asaf Karagila Nov 26 '11 at 15:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ "Derangement" is the term. $\endgroup$ – Quixotic Nov 26 '11 at 15:02
  • $\begingroup$ I agree my question is a duplicate and should be merged. However, the linked question has no accepted answer ( and IMHO, its title could be better worded). Is there a way those things could be rectified? $\endgroup$ – Mark Borgerding Nov 26 '11 at 15:13
  • $\begingroup$ Sure, you can always edit any answer/question. $\endgroup$ – Quixotic Nov 26 '11 at 15:16
  • $\begingroup$ @Mark: we're working on a nice big CW question covering derangements/subfactorials. I'll ping you when it's ready. $\endgroup$ – J. M. is a poor mathematician Nov 26 '11 at 16:57
  • $\begingroup$ @J. M.:Exactly who are "we"? :) $\endgroup$ – Quixotic Nov 26 '11 at 19:39

This is a classical problem.

You can either search the wikipedia article for permutations for "fixed points" to find the link to the correct article that contains all the information:


or, if you like programming, you can use the encyclopedia of integer sequences to find information on a sequence:



Not the answer you're looking for? Browse other questions tagged or ask your own question.