Assume an ordered list $L$ of distinct natural numbers $L_1, L_2, ..., L_n$.
Sort the list. What is the expected number $E(n)$ of elements which stay in the same position? I've been working through an intuition for it, but can't fix it into an inductive proof.
The base case is simple: a list of length 1 has an expected value of 1: it must be in order.
A list of length 2, likewise, has an expected value $E(2)$ of 1: there are two permutations of the elements: one with both in the correct positions and one with none in the correct positions.
With three elements, there are six permutations. One has 3 elements in correct positions, three have 1 element in the correct positions, and two have none. The expected value $E(3)$ is 1, too.
Why is there this regularity?
The expected number is always $1$.
Let $N$ be the number of the $L_i$ which do not move after ordering them. Let $I_i$ be the indicator that $L_i$ does not move, i.e., $I_i=1$ if $L_i$ does not move, and otherwise it is $0$. Then $N=I_1+\cdots+I_n$, and $$E[N]=E\left[\sum_{i=1}^n I_i\right]=\sum_{i=1}^n E[I_i] = \sum_{i=1}^n P(I_i).$$ Now the probability that $L_i$ does not move is the number of permutations of $L_1,\dots,L_n$ in which $L_i$ is in the spot it will be after rearranging (i.e., $(n-1)!$), divided by the total number of permutations of $L_1,\dots,L_n$ (i.e., $n!$). Thus $P(I_i)=\frac{(n-1)!}{n!}=\frac{1}{n}$. So, finally, $\sum_{i=1}^n P(I_i)=\sum_{i=1}^n \frac{1}{n}=1$.