1

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

Michael Albanese
  • 99,526
user2553807
  • 1,245
  • 25
  • 46
  • The case $n=9$ is here: http://math.stackexchange.com/questions/570846/permutations-and-derangements –  Nov 18 '13 at 02: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 04: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 05:03

1 Answers1

-1

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.

Akshara
  • 80