Uniform random permutation ($P(\pi )=1/n!$)

A uniform random permutation of $n$ distinct objects gives each of the $n!$ permutations the same probability. Restricting the order to any fixed subset gives a uniform ordering on that subset. Relative ranks encode such a permutation bijectively by independent choices of an insertion position.

For a uniform random permutation $a_1,\dots ,a_n$, define $R_i$ as the rank of $a_i$ among $a_1,\dots ,a_i$, with rank one assigned to the smallest value. Each sequence $r_i\in \{1,\dots ,i\}$ corresponds to exactly one permutation: insert index $i$ in position $r_i$ of the current increasing-value list, then assign the final list the values $1,\dots ,n$. The $n!$ equally likely permutations therefore correspond to the ${\prod }_{i=1}^{n}i=n!$ equally likely rank sequences. Consequently the $R_i$ are independent random variables, each with the displayed uniform distribution.

The indicators $Y_i=1_{\{R_i=1\}}$ of successively smaller records are independent and have Bernoulli distributions of parameters $1/i$. Successively larger records use $R_i=i$ and have the same laws. For $K_n={\sum }_{i=1}^n{Y}_i$, expectation and variance additivity for independent random variables give $E{K}_n={\sum }_{i=1}^{n}1/i$ and $\mathrm{Var}{K}_n={\sum }_{i=1}^n(1/i-1/i^2)$.

For a uniform random permutation $\pi$ of $n\ge 1$ objects, let $M_n$ count its fixed points. Write $M_n={\sum }_{i=1}^n{1}_{\{\pi (i)=i\}}$. Each indicator random variable has expected value $1/n$, so linearity of expectation gives $\mathbb{E}[M_n]=1$ for every $n\ge 1$. This average does not require independence: for $n\ge 2$, 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\cdot 9+1\cdot 8+2\cdot 6+4\cdot 1)/24=1$. Exactly three fixed points are impossible: the last object must then also be fixed.

Choose the $m$ fixed objects and derange the remaining $n-m$. Their count is $\left(\genfrac{}{}{0ex}{}{n}{m}\right)D_{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.