Determine the number of permutations of $\{1, 2, \dots, n\}$ in which no odd integer is in its natural position.

I'm having a hard time generalizing this situation for $\{1, 2, \dots, n\}$

When there is a finite set, for example $\{1, 2, \dots, 6\}$, I know that I will have $$6!-\binom{3}{1}5!+\binom{3}{2}4!-\binom{3}{3}3!$$

Any advice of how to generalize this situation?

Would it be something like $$\sum_{k=0} (-1)^k \binom{n/2}{k+1} (n-1)!$$

  • $\begingroup$ The case $n=9$ is here: math.stackexchange.com/questions/570846/… $\endgroup$ – user940 Nov 18 '13 at 2:56
  • $\begingroup$ I would sum over subsets of the even integers between $1$ and $n$, counting the derangements of the complements. Of course equal size subsets (of these even integers) give equal size complements, so those contributions to the final sum can be lumped together. $\endgroup$ – hardmath Nov 18 '13 at 4:52
  • $\begingroup$ The fact that the even integers may or may not be fixed is not specially important here. A very similar problem was posed recently (~two months ago). I believe a better Answer can be given to that more general one, along the lines in my Comment above. $\endgroup$ – hardmath Nov 18 '13 at 5:03

Consider arranging the odd integers of the given sequence (1,3,5,7,9,............,n-1 or n) in n spaces, such that none of them occupies the same position as thier numerical value (i.e., 1 doesn't stay in the first position, or 3 in the third, and so on.)

  • You'll have to choose a position for (1) from n positions other than the first position. This can be done in n-1 ways.

    Similarly, (3) can be anywhere other than in the third position or the chosen position for (1).There are n-2 ways of assigning a position to (3).

  • There are n/2 odd numbers in the sequence if n is even and n+1/2 odd numbers if n is odd.

Having placed all but the last (odd) number,

1)if n is odd, there are n-1/2 ways to place the last number. Hence, there are (n-1)!/(n-3/2)! ways to arrange the odd integers. So, there are (n-1/2)!.(n-1)!/(n-3/2)! ways of permutating all the numbers in the sequence 1,2,3,.....n (since there will be n-1/2 even numbers).

2)if n is even, there are n/2 ways to place the last odd number. So, there are (n-1)!/(n-2/2)! ways of arranging the odd numbers and (n/2)!.(n-1)!/(n-2/2)! total ways of permutating all the numbers in the sequence.


Your Answer

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

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