count number of permutation that map no even number to itself

Question

Problem: How many permutations of numbers $1, 2, ..., 10$ exist that map no even number to itself?

I understand that this is "Hatcheck lady" problem. But I am a bit confused how to solve it. So my solution:

$D_{i}$ = no even number map to itself

$i$ = even number map to itself

At total there is $10!$ possibilities. There are ${10 \choose 5}$ possibilities to choose an even number (or not?). Then there are ${10 \choose 5}D_{10-5}$ possibilities. And so $n! = \sum_{i=0}^{n} {10 \choose 5}D_{10-5}$. And then put this in from of this formula: $\displaystyle D_n = n! \left({1 - \frac 1 {1!} + \frac 1 {2!} - \frac 1 {3!} + \cdots + \left({-1}\right)^n \frac 1 {n!} }\right)$

I am right? Or something is completely wrong?

Answer 1

Outline: Call a permutation bad if it maps some even number to itself. We count the bad permutations.

There are $9!$ permutations that map $2$ to itself, and $9!$ that map $4$ to itself, and so on.

Add up. We get that our first estimate for the number of bad permutations is $5\cdot 9!$, which with an eye to the future we call $\binom{5}{1}9!$.

This first estimate is too large, since for every unordered pair $\{i,j\}$ of even numbers, we have double-counted the $8!$ permutations that send $i$ and $j$ to themselves. So our next estimate of the number of bad permutations is $\binom{5}{1}9!-\binom{5}{2}8!$.

But we have subtracted too much, for we have subtracted one too many times the $\binom{5}{3}7!$ permutations that send some specific three even numbers to themselves. So our next estimate for the number of bad permutations is $\binom{5}{1}9!-\binom{5}{2}8!+\binom{5}{3}7!$.

But we have added back too much. Continue, we are close to the end.

Remark: We could have used the same technique to count the number of good permutations directly, getting first term $10!$, from which we subtract $\binom{5}{1}9!$, then adding back $\binom{5}{2}8!$, and so on. For some reason I find it easier to focus on the bads.

Answer 2

By the inclusion-exclusion principle the answer is $\sum\limits_{i=0}^n(-1)^i(2n-i)!\binom{n}{i}$

there are $2n!$ permutations in general.

Although from these we need to substract those which send any given element to itself. There are $\binom{n}{1}$ ways to select that element and there are $(2n-1)!$ permutations that fix any given element, so we must substract $(2n-i)!\binom{n}{i}$ to the count.

Except now we have oversubstracted since we have substracted permutations that fix more than one even number more than once. Since there are $\binom{n}{2}$ such pairs of even numbers and there are $(2n-2)!$ permutations that fix any two of them we must add back $\binom{n}{2}(2n-2)!$ to the count, and so on...(this is the general argument for inclusion exclusion).