# How many ways to permute a sequence leaving no element in its starting position? [duplicate]

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

• "Derangement" is the term. – Quixotic Nov 26 '11 at 15:02
• 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? – Mark Borgerding Nov 26 '11 at 15:13
• Sure, you can always edit any answer/question. – Quixotic Nov 26 '11 at 15:16
• @Mark: we're working on a nice big CW question covering derangements/subfactorials. I'll ping you when it's ready. – J. M. is a poor mathematician Nov 26 '11 at 16:57
• @J. M.:Exactly who are "we"? :) – Quixotic Nov 26 '11 at 19:39