Combinatorics, No-Match Permutations

No-Match Permutations

The number of n-element permutations that never map an element to itself can be determined using the principle of inclusion exclusion. The number of "no match" permutations is the total number of permutations, minus the permutations with at least one match, plus the permutations with at least two matches, minus the permutations with at least three matches, etc. In other words, we have the alternating sum of n!/i!. Factoring out n! leaves the beginning of the taylor expansion for exp(-1). Thus the number of no-match permutations approaches n!/E.