Nice: find number of even permutations with no fixed points

freemind

Nice: find number of even permutations with no fixed points

**Posted:** Sat Mar 29, 2008 4:49 pm

_________________
The fate of equilibrium is to end the eternity...

pohoatza

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.

**Posted:** Sat Mar 29, 2008 8:42 pm

_________________
Cosmin Pohoata, Bucharest, Romania