= Fixed point count of a uniform random permutation
{title2=$P(M_n=m)=\dfrac1{m!}\sum_{j=0}^{n-m}\dfrac{(-1)^j}{j!}$}
For a <uniform random permutation> $\pi$ of $n\geq1$ objects, let $M_n$ count its <fixed points>. Write $M_n=\sum_{i=1}^n\mathbf1_{\{\pi(i)=i\}}$. Each <indicator random variable> has <expected value> $1/n$, so <linearity of expectation> gives \b[$\mathbb E[M_n]=1$ for every $n\geq1$]. This average does not require <independence>: for $n\geq2$, fixing two specified objects has <probability> $1/[n(n-1)]$, greater than the product $1/n^2$ of their individual <probabilities>.
For four objects, exact enumeration gives counts $9,8,6,0,1$ for $0,1,2,3,4$ <fixed points> among the $24$ equally likely <permutations>. Their weighted <arithmetic mean> is $(0\cdot9+1\cdot8+2\cdot6+4\cdot1)/24=1$. Exactly three <fixed points> are impossible: the last object must then also be fixed.
\Image[/fixed-points-permutation-expectation.png]
{title=The <fixed point count of a uniform random permutation> averaged over all $24$ <permutations> of four objects}
{description=Each card lists $\pi(1),\pi(2),\pi(3),\pi(4)$. Green entries equal their positions and therefore mark <fixed points>. The <probability mass function> on the right counts those cards; its <expected value> is one.}
Choose the $m$ fixed objects and derange the remaining $n-m$. Their count is $\binom nmD_{n-m}$ among $n!$ equally likely <permutations>. The <inclusion-exclusion principle> for $D_{n-m}$ proves the displayed law, valid for $0\le m\le n$ and zero otherwise. With $D_0=1$, it includes the all-fixed case and the impossibility of exactly $n-1$ fixed objects. For fixed $m$, the law tends to $e^{-1}/m!$, the <Poisson distribution> of mean one.
Back to article page
