Think of a permutation on n elements as a function {1,...,n} → {1,...,n}. It makes sense to count how many fixpoints this function has. There are n! permutations. How many permutations have no fixpoints? All the rotations, for a start, but obviously many more.

We may calculate a formula for this number using Poincaré's inclusion / exclusion principle. Note that the proportion of permutations fixing some specified point is 1/n, and, in general, 1/(n⋅(n-1)⋅...⋅(n-k+1)) of the permutations fix some k specified points.

By the inclusion / exclusion principle, the number of permutations with no fixpoints is

n! - a1*(n-1)! + a2*(n-2)! + ... + (-1)kak*(n-k)! + ...,
where ak=n!/(k!(n-k)!) is the number of ways to select k points. Cancelling, we see that the number is precisely
n! * (1/0! - 1/1! + 1/2! - 1/3! + 1/4! - ... + (-1)n/n!)

Note that the numbers in the brackets converges very rapidly to 1/e (where e=2.718281828459045... is Napier's constant, the base for natural logarithms). So it is fair to say that approximately 1/e of all permutations have no fixpoint. In fact, the exact number is the closest integer to n!/e.

Log in or registerto write something here or to contact authors.