show/hide this revision's text 3 tweaks

  1. The mean number of fixed points is 1. This is very elementary.

  2. Consider the operation of rotating three values around: $p(i)\to p(j)\to p(k)\to p(i)$. Given a permutation with no fixed points, there are $n^2-O(n)$ rotations that create from it a permutation with exactly one fixed point. Given a permutation with exactly one fixed point, there are $n^2-O(n)$ rotations that create from it a permutation with no fixed points.

  3. From (2), the number numbers of permutations with 0 and 1 fixed points are the same to $O(1/n)$ relative error. Combining this with (1) shows that the fraction of permutations with no fixed points is at least $\frac13-O(1/n)$.

This is the switching method and it can be used in extremely many circumstances. By continuing to increase the number of fixed points by further switchings, step 1 could be avoided.

Incidentally, congratulations to Terry and Jean Bourgain.
show/hide this revision's text 2 add irrelevant comment

  1. The mean number of fixed points is 1. This is very elementary.

  2. Consider the operation of rotating three values around: $p(i)\to p(j)\to p(k)\to p(i)$. Given a permutation with no fixed points, there are $n^2-O(n)$ rotations that create a permutation with exactly one fixed point. Given a permutation with exactly one fixed point, there are $n^2-O(n)$ rotations that create a permutation with no fixed points.

  3. From (2), the number of permutations with 0 and 1 fixed points are the same to $O(1/n)$ relative error. Combining this with (1) shows that the fraction of permutations with no fixed points is at least $\frac13-O(1/n)$.

This is the switching method and it can be used in extremely many circumstances. By continuing to increase the number of fixed points by further switchings, step 1 could be avoided.

Incidentally, congratulations to Terry and Jean Bourgain.
show/hide this revision's text 1

  1. The mean number of fixed points is 1. This is very elementary.

  2. Consider the operation of rotating three values around: $p(i)\to p(j)\to p(k)\to p(i)$. Given a permutation with no fixed points, there are $n^2-O(n)$ rotations that create a permutation with exactly one fixed point. Given a permutation with exactly one fixed point, there are $n^2-O(n)$ rotations that create a permutation with no fixed points.

  3. From (2), the number of permutations with 0 and 1 fixed points are the same to $O(1/n)$ relative error. Combining this with (1) shows that the fraction of permutations with no fixed points is at least $\frac13-O(1/n)$.

This is the switching method and it can be used in extremely many circumstances. By continuing to increase the number of fixed points by further switchings, step 1 could be avoided.