The Expected Number of Fixed Points

Problem

The Expected Number of Fixed Points

Solution 1

The expected number in question that we shall denote $E(N)$ equals

$\displaystyle E(n)=\sum_{k=0}kq_k,$

where $q_k$ is the probability of there being exactly $k$ fixed points. The number of permutations with exactly $k$ fixed points is the number of ways of choosing $k$ points out of $n$ times the number of derangements of the remaining $n-k$ points. It follows that

$\displaystyle q_k=\frac{\displaystyle {n\choose k}\cdot !(n-k)}{n!},$

where $!m$ is the subfactorial of $m$, the number of derangements of a set of $m$ elements. Thus, with a substitution $m=n-k$ and using the symmetry of the binomial coefficients, ${n\choose n-m}={n\choose n},$

$\displaystyle\begin{align}E(n)&=\sum_{k=0}k\cdot\frac{\displaystyle {n\choose k}\cdot !(n-k)}{n!}=\sum_{m=0}^n(n-m)\frac{\displaystyle {n\choose m}\cdot !m}{n!}\\ &=\sum_{m=1}^n(n-m)\frac{\displaystyle {n\choose m}\cdot !m}{n!}=\sum_{m=1}^n(n-m)\frac{(n-m)\cdot !m}{m!(n-m)!}\\ &=\frac{!m}{m!(n-m-1)!}. \end{align}$

Multiplying both sides by $(n-1)!,$

(*)

$\displaystyle\begin{align}(n-1)!\cdot E(n)&=\sum_{m=1}^n(n-m)\frac{(n-1)!}{m!(n-m-1)!}\cdot !m\\&=\sum_{m=1}^n{n-1\choose m}\cdot !m.\end{align}$

But it is easily seen that $\displaystyle \sum_{m=1}^n{n-1\choose m}\cdot !m=(n-1)!$ because every permutation has a certain number of fixed points with the remaining points deranged. (As above but with $n-1$ points, there are $\displaystyle {n-1\choose n-m-1}\cdot !m={n-1\choose m}\cdot !m$ permutations with $m$ fixed points.) Thus, from $\displaystyle (n-1)!\cdot E(n)=(n-1)!$ we get $E(n)=1,$ independent of $n.$

Solution 2

Use indicator functions $\mathbb{I}(k)= 1$ if fixed point at $k,$ $0$ otherwise. $\displaystyle E[\mathbb{I}(k)]=\frac{1}{n}$ for each $k.$ By the additivity of the expected value, $\displaystyle E(n)=\sum_{k=1}^nE[\mathbb{I}(k)]=n\cdot\frac{1}{n}=1.$

Solution 3

Of $n!$ permutations, $(n-1)!$ fix a particular point. Thus, total number of fixed points over all perms is $n\times (n-1)!.$ It follows that the expected number is $\displaystyle \frac{n \times (n-1)!}{n!} = 1.$

Acknowledgment

Solution 1 follows the discussion in Chapter 5 of Nonplussed! Mathematical Proof of Implausible Ideas by J. Havil (Princeton University Press, 2007).

Solution 2 is by Roland van Gaalen; Solution 3 is by Amit Itagi.

 

|Contact| |Front page| |Contents| |Probability|

Copyright © 1996-2018 Alexander Bogomolny

71491397