# Combinatorics and Derangements

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)!$$

• The case $n=9$ is here: math.stackexchange.com/questions/570846/… – user940 Nov 18 '13 at 2:56
• 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. – hardmath Nov 18 '13 at 4:52
• 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. – hardmath Nov 18 '13 at 5:03

## 1 Answer

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.