Can we use derangements here?

Question

Determine the number of permutations of $\{1,2,....,9 \}$ in which at least one odd integer is in its natural position.

We have $5$ odd integers right, which is $1,3,5,7,9$

Now I think about it in terms of derangements. And so for example if we have exactly one odd integer in it's natural position then we have ${5 \choose 1}$ ways to choose this odd integer and we have $d(8)$ ways to derange the other integers right, so we have ${5 \choose 1} d(8)$

Now if we have two odd integers in their natural position so we have ${5 \choose 2} d(7)$ and so on so my answer will be the following

$${5 \choose 1}d(8) + {5 \choose 2}d(7) + {5 \choose 3}d(6) + {5 \choose 4} d(5) + {5 \choose 5}d(4)$$

and this will gives the total number of ways that we have at least one integer in it's natural position. Is that true !!

But the problem is, we don't necessarily want to derange all other integers so I guess my answer will fail.

What do you think guys ?

I also thought about deranging the odd integers and permuting the even integers so I thought maybe we will have something like the following:

If we have exactly one integer in it's natural position so I have to derange the other $4$ odd integers and permute the even integers so I will have $${5 \choose 1} d(4) 4!$$

and in the case where I have exactly two odd integers in their natural position so I have to derange the other 3 odd integers and still I have to permute the 4 even integers so I will have

$${5 \choose 2} d(3) 4!$$ and so on And so my answer in this case will be

$${5 \choose 1}d(4)4! + {5 \choose 2}d(3)4! + {5 \choose 3}d(2)4! + {5 \choose 4} d(1)4! + {5 \choose 5}d(0)4!$$

Is any of these answers true ?

I feel like the second answer is more logical as it reflects the fact that we don't really need to derange the even integers.

Answer 1

Using Inclusion-Exclusion, we get $$ \sum_{k=1}^5(-1)^{k-1}\binom{5}{k}(9-k)!=157824 $$ Permutations with at least one odd number in its original position.

To count the number of arrangements with $k$ odd numbers in their original place, there are $\binom{5}{k}$ ways to choose $k$ odd numbers, and for each choice, there are $(9-k)!$ ways to permute the other numbers. This is the size of the intersection of $k$ of the sets $S_1,S_3,S_5,S_7,S_9$ where $S_j$ is the collection of permutations fixing $j$.

Answer 2

I'd suggest not using derangements, but rather just inclusion-exclusion. Define sets $A_1, A_3, A_5, A_7, A_9$ where $A_1$ is the set of permutations with $1$ in its natural position, etc.

Then we want $\mid A_1\cup A_3\cup A_5 \cup A_7 \cup A_9 \mid$.

I think you should be able to get this with a fairly straightforward application of the inclusion-exclusion principle.

Answer 3

The problem with your first method, as you point out, is that you don't necessarily want to derange the even integers. But there's another issue that afflicts your second method, and that's that derangement of the non-fixed odd integers isn't the only possibility. Another thing that can happen is to put even integers in odd positions and odd integers in even positions. So there are a lot of possibilities that neither of your expressions accounts for.

In conclusion, I don't think derangements can easily be used here. You would instead need to come up with an expression for the number of permutations such that none of the non-fixed odd integers is in its natural position. But that's equivalent to the original problem! So back to square one. The inclusion-exclusion method given in the other answers is the way to go.