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 Trainer Apr 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.

  • $\begingroup$ 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$? $\endgroup$ – Arthur Apr 11 at 14:09
  • $\begingroup$ @Arthur You right but in fact i couldn't even understand the question well $\endgroup$ – Developer Apr 11 at 14:46
  • $\begingroup$ @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\}$? $\endgroup$ – Luiz Cordeiro Apr 11 at 15:03
  • $\begingroup$ 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!$. $\endgroup$ – Arthur Apr 11 at 15:10
  • $\begingroup$ Please add context to your question. A short question body will trigger an alarm. $\endgroup$ – 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".


Not the answer you're looking for? Browse other questions tagged or ask your own question.