# Average distance moved by a permutation [closed]

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?

## closed as off-topic by Saad, GNUSupporter 8964民主女神 地下教會, Xander Henderson, RRL, Eevee TrainerApr 13 at 5:20

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, GNUSupporter 8964民主女神 地下教會, Xander Henderson, RRL, Eevee Trainer
If this question can be reworded to fit the rules in the help center, please edit the question.

• Often, looking at smaller examples can help you uncover patterns that help you solve larger examples. Have you tried calculating the average for, say, $n = 2, 3$ or $4$? – Arthur Apr 11 at 14:09
• @Arthur You right but in fact i couldn't even understand the question well – Developer Apr 11 at 14:46
• @Developer The question is asking: What is $\frac{1}{7!}\sum_\pi f(\pi)$, where $\pi$ in the sum runs through all permutations of $\left\{1,\ldots,7\right\}$? – Luiz Cordeiro Apr 11 at 15:03
• Say $\pi$ is the cyclic permutation that sends $k\mapsto k+1$, except $7\mapsto 1$. Then $$f(\pi)=1+1+1+1+1+1+6=12$$ You are asked to calculate this value for all different $\pi$, sum them up, and divide by $7!$. – Arthur Apr 11 at 15:10
• Please add context to your question. A short question body will trigger an alarm. – GNUSupporter 8964民主女神 地下教會 Apr 11 at 15:20

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".