Averaging over All Permutations via Linearity of Expectation

To average a permutation statistic over all of $S_n$, write it as a sum of indicators and use linearity of expectation — one object at a time.