Average distance moved by a permutation For each $\pi$ permutation of numbers 1 to n, $f(\pi) = \sum_{i=1}^n |\pi_i - i|$. What is the average of $f(\pi)$ on all of the $n=7$ permutations?
 A: Let's do this for a general $n$, instead of $7$.  
We have $$E(f(\pi)) = E \left( \sum_{i=1}^n |\pi_i - i| \right).$$ By linearity of expectation, we get
$$ E(f(\pi)) = \sum_{i=1}^n E(|\pi_i - i|). $$
Now $E(|\pi_i - i|)$ of course depends on $i$ and $n$. In particular, we have
$$ E(|\pi_i - i|) = {(i-1) + (i-2) + \cdots + 1 + 0 + 1 + \cdots + (n-i) \over n}. $$
Then we have $(i-1) + (i-2) + \cdots + 1 = i(i-1)/2$ and $1 + 2 + \cdots + (n-i) = (n-i)(n-i+1)/2$.  This gives
$$ E(|\pi_i - i|) = {i(i-1)/2 + (n-i)(n-i+1)/2 \over n} $$
Therefore, going back to the initial sum, $$E(f(\pi)) = \sum_{i=1}^n {i(i-1) \over 2n} + \sum_{i=1}^n {(n-i)(n-i+1) \over 2n}.$$
These tw sums are the same since they have the same terms in reverse order, so we get
$$ E(f(\pi)) = 2 \sum_{i=1}^n {i(i-1) \over 2n} = {1 \over n} \sum_{i=1}^n i^2-i$$
Finally we can work out that sum:
$$ {1 \over n} \sum_{i=1}^n (i^2-i) = {1 \over n} (\sum_{i=1}^n i^2 - \sum_{i-1}^n i) = {1 \over n} \left( {n(n+1)(2n+1) \over 6} - {n(n+1) \over 2} \right) = (n+1) \left( {2n+1 \over 6} - {1 \over 2} \right) = {(n+1)(2n-2) \over 6} = {n^2 - 1 \over 3}.$$
The references at https://oeis.org/A062869 appear to be relevant; the statistic computed here is called the "total displacement" of a permutation or "Spearman's disarray".
