Fixed points in random permutation [closed]

Solution 1:

Let random variable $X_i$ be defined by $X_i=1$ if $i$ is a fixed point of the permutation, and by $X_i=0$ otherwise. Then the number $W$ of fixed points is given by $W=X_1+\cdots+X_n$.

By the linearity of expectation we have $E(W)=E(X_1+\cdots+X_n)=E(X_1)+\cdots+E(X_n)$.

The probability that $X_i=1$ is $\frac{1}{n}$. Thus the expected number of fixed points is $n\cdot\frac{1}{n}$, that is, $1$.

Remarks: $1$. If we want to find the expected number of common fixed points of two random permutations, the same technique works. Let $Y_i=1$ if $i$ is a common fixed point of the two permutations. Then the number of common fixed points is $Y_1+\cdots +Y_n$. We have $\Pr(Y_i=1)=\frac{1}{n^2}$, so the expected number of common fixed points is $\frac{1}{n}$.

$2$. The random variables $X_i$ of the answer are not independent. However, expectation is linear in all cases. The above method of indicator random variables bypasses the problem of finding the distribution of $W$.