What's the name of this quantity?

Solution 1:

Let $n=2m$. Take any permutation where if $n\leq m$ then $\sigma(n)>m$ and if $n>m$ then $\sigma(n)\leq m$. Then $\sum_{(k=i)}^m|\sigma(m)-i|=\sum_{(k=i)}^m\sigma(m)-i=m^2$ and $\sum_{(i=m+1)}^{2m}|\sigma(m)-i|=\sum_{(i=m+1)}^{2m}i-\sigma(m)=m^2$.

Now suppose you have a permutation that does not satisfy this. Then it has a pair $i,j$ where $i,\sigma(i)\leq m$ and $j,(\sigma(j)>m$. Show switch $\sigma(i)$ and $\sigma (j)$ makes the distance sum larger.

Do the same for the other side to get:

For $n=2m+1$ this is $m(2m+2)$. For $n=2m$ this is $2m^2$

enter image description here For a geometrical interpretation See that if $\sigma(m)$ and $(m)$ and $\sigma(j)$ and $j$ are on different sides then the distance between them is more than $DE+FG$