View topic - Nice: find number of even permutations with no fixed points • Art of Problem Solving

It is known that an even permutation of this kind is called an even derrangement. In the following, for sake of clarity, denote by $O_{n}$ , $E_{n}$ , and $D_{n}$ the numbers of odd, even, and all derangements of the $n$ numbers. Now, I shall figure out a connection between $O_{n}$ and $E_{n}$ , the conclusion following then from the obvious fact that $O_{n} + E_{n} = D_{n}$ .

First, it is clear that $E_{1} = O_{1} = 0$ , $E_{2} = 0$ , $O_{2} = 1$ . From the initial ordering of the $n$ numbers, interchange the first and the $j$ -th numbers. There will be $E_{n - 2}$ derangements of the remaining $n - 2$ letters which lead to odd derangements of the entire set. Since $j$ may be any one of the integers $2$ , $3$ , $\ldots$ , $n$ , there are $(n - 1)E_{n - 2}$ odd derangements of this type. Again, starting with the original arrangement of the $n$ integers, consider the first one followed by any one of the $E_{n - 1}$ even derangements of the last $n - 1$ numbers. Now interchange the two numbers from the first and $j$ -th positions, and we obtain an odd derangement of all $n$ numbers. There are $(n - 1)E_{n - 1}$ odd derangements of this type. Thus, $O_{n} = (n - 1)(E_{n - 1} + E_{n - 1})$ , and likewise, $E_{n} = (n - 1)(O_{n - 1} + O_{n - 2})$ .
In conclusion, by a small induction, one can deduce that $O_{n} - E_{n} = ( - 1)^{n}(n - 1)$ , and since $O_{n} + E_{n} = D_{n}$ , we have that $E_{n} = \frac {1}{2}(D_{n} + ( - 1)^{n-1}(n - 1))$ , where $D_{n} = n!\left(1 - \frac {1}{1!} + \ldots + \frac {( - 1)^{n}}{n!}\right)$ , as a consequence, for example, of the Inclusion-Exclusion Principle.

I suspect that my approach is far from beeing new, but this is what I've found. I am also aware of a solution using some linear algebra, from "Recounting the Odds of an Even Derangement", Mathematics Magazine.

Nice: find number of even permutations with no fixed points

Login