Expected Positions Exceeding Values in a Random Permutation

Expectation · Easy · Free problem
A permutation $\sigma$ of $\{1, 2, \dots, n\}$ is chosen uniformly at random. An index $i$ is called a "winner" if $\sigma(i) > i$ -- that is, the value at position $i$ is strictly larger than $i$ itself. What is the expected number of winners? Give a general formula in terms of $n$, then evaluate it for $n = 25$.

Open the full interactive solver, hints, and worked solution →