Derangement in a transitive group action ($\mathrm{Fix}(g)=\varnothing$)

A derangement is an element fixing none of the points of a group action. Every finite transitive action on at least two points has a derangement. Count pairs $(g,x)$ with $gx=x$: transitivity gives ${\sum }_g|\mathrm{Fix}(g)|={\sum }_x|G_x|=|G|$. If every element fixed a point, the identity's extra fixed points would make this sum strictly larger than $|G|$. This is the Burnside lemma counting argument specialized to existence of a derangement.

Inclusion-exclusion applied to the events that a permutation fixes a specified point gives the displayed formula. There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ choices of $k$ fixed points and $(n-k)!$ permutations fixing them. The probability that a uniformly chosen permutation is a derangement tends to $e^{-1}$.

// Target: analysis.bigb