What's the name of this quantity?

Question

For each permutation $\sigma$ of $ \left\{ 1, 2, \dots, n \right\}$ define $$\operatorname{dist}(\sigma)=\sum_{i=1}^{n}\left| \sigma (i)-i \right|$$ For each $n\in\mathbb{N}$, I'm interested in finding the maximum value this function can score, namely $$M_n=\max_{\sigma\in D_n}\left\{\operatorname{dist}(\sigma)\right\}$$

Does $M_n$ has a conventional name? Uses? Is there a formula to find it?

I've noticed that $M_n$ grows "in pairs", meaning that for each odd $a\in \mathbb{N}$ it holds that $$M_{a+1}-M_a=M_{a+2}-M_{a+1}$$

I guess it can represent some kind of measure for hardness to sort.

We have $M_n \ge \lfloor n^2/2 \rfloor$, since $dist(\sigma_n) = \lfloor n^2/2 \rfloor$ when $\sigma_n$ is the ``reverse'' permutation $n(n-1)(n-2) \ldots 1$. This is the sequence http://oeis.org/A007590. But I can't prove that this is an equality. — Michael Lugo, Dec 31 '13 at 19:27
Why does the "reverse" permutation yields $M_n$? I think it's true. — Amihai Zivan, Dec 31 '13 at 19:35
See this paper which gives a lot of information on the statistic they call "depth" which is $\frac{1}{2}\operatorname{dist}(\sigma)$. They give bounds as well as a connection to sorting. — Jair Taylor, Jan 03 '14 at 20:34
In computer science $\operatorname{dist}(\sigma)$ is known as the "dislocation distance" or "total dislocation" [Braverman and Mossel 2008, Geissmann et al. 2017]. — , Dec 02 '17 at 21:40
This paper calculates this quantity, as well as a generalization when permuting any finite subset of the reals. — Dominik Peters, Jun 19 '20 at 04:32

Asinomás · Accepted Answer · 2014-01-01T15:50:00.037

3

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$

edited Jan 01 '14 at 15:50

answered Dec 31 '13 at 20:01

Asinomás

105,651

The distance doesn't necessarily grow if you swap $\sigma(m)$ and $\sigma(k)$, it can remain the same as well. For example, take permutation $3,4,1,2$ which also attains the maximum total distance. – Peter Košinár Dec 31 '13 at 20:05
Thanks, I think it is correct now. – Asinomás Dec 31 '13 at 20:27
@user4140 care to explain more? I didn't quite understand. – Amihai Zivan Jan 01 '14 at 08:44
2

If a permutation sends elements from one side to the other then they have the same distance sum. Suppose a permutation dos not send all elements in one side to the other. Then we have a pair of elements where $k,\sigma(k)\leq m$ and $j,\phi(j)>m$. I'll add a drawing. – Asinomás Jan 01 '14 at 15:44
1

FYI, the quantity $\operatorname{dist}(\sigma)$ is called Spearman's footrule distance. – Mike Spivey Jan 01 '14 at 21:39

What's the name of this quantity?

1 Answers1

Linked

Related