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