Csdrhrt

Let $S_{n}$ denote the set of permutations of the sequence from $(1,2,dots,n)$.
Let us define a metric on $S_{n}$ for any $sigma, tauin S_{n}$, such that $$d(sigma,tau)=sum_{i=1}^{n}vertsigma(i)-tau(i)vert$$. What are the values of $d(sigma,tau)$ can be?

Any ideas from which point should I start?

This is not an answer but too long for a comment:

Let $D_n$ be the range of $d$ under $S_n$. A quick and dirty implementation in python

import itertools

n = 4

domain = range(1, n+1)

perm = list(itertools.permutations(domain))

values = set()



for i in perm:

    for j in perm:

        x = 0

        for k in range (0, n):

            x += abs(i[k] -j[k])

        values.add(x)



return values

yields that
$$
begin{align*}
D_1 &= {0} \
D_2 &= {0,2 } \
D_3 &= {0,2,4 } \
D_4 &= {0,2,4, 6, 8} \
D_5 &= {0,2,4,6,8,10,12 } \
D_6 &= {0,2,4,6,8,10,12,14,16,18 } \
D_7 &= {0,2,4,6,8,10,12,14,16,18,20,22,24 }
end{align*}
$$

It's also easy to show that $D_n subseteq D_{n+1}$ and that ${0,2, ldots, 2 cdot (n-1) } subseteq D_{n+1}$ (for all $n$). However, I'm not sure where the extra values in the steps $3 mapsto 4$, $4 mapsto 5$, $5 mapsto 6$, $6 mapsto 7$ come from.

The value of $d(sigma,tau)$ can be any even integer between $0$ and $leftlfloorfrac{1}{2}n^2rightrfloor$. In fact, given an even integer $k$ within these bounds, one can explicitly construct a permutation $sigma$ with $d(sigma,Id)=k$, where $Id$ denotes the identity permutation (we will abuse the notation slightly and use the same name for all identity permutations, regardless of the value of $n$).

We will prove this in an induction-like fashion:

• If $nleq 2$, the problem is trivial. From now on, we'll assume $ngeq 3$.


• If $k < 2(n-1)$, we can deduce that $kleq 2(n-1)-2$ (due to $k$ being an even integer) and a short calculation tells us that:
  $$begin{eqnarray}
  0 & leq & (n-3)^2 \
  0 & leq & (n-1)^2 - 4n + 8\
  2(n-1) - 2 & leq & frac{1}{2}(n-1)^2 \
  k & leq & leftlfloorfrac{1}{2}(n-1)^2rightrfloor \
  end{eqnarray}$$
  where the floor function could have been introduced thanks to the left-hand side of the inequality being an integer. The last inequality allows us to apply the induction hypothesis to obtain a permutation $sigma$ on $(n-1)$ elements having $d(sigma,Id)=k$ and extend it by setting $sigma(n)=n$ to obtain a permutation on $n$ elements with the desired property.


• Finally, if $kgeq 2(n-1)$, we find a permutation $sigma'$ on $(n-2)$ elements with $d(sigma',Id)=k-2(n-1)$ by the induction hypothesis. This can be done because $$begin{eqnarray}
  k-2(n-1) & leq & leftlfloor frac{1}{2}n^2rightrfloor - 2(n-1)\
  & = & leftlfloor frac{1}{2}left(n^2 - 4n + 4right)rightrfloor\
  & = & leftlfloor frac{1}{2}left(n-2right)^2rightrfloor
  end{eqnarray}$$
  Now, we can define our permutation $sigma$ as $sigma(1)=n$, $sigma(n)=1$ and $sigma(i)=sigma'(i-1)+1$ for $1<i<n$. Doing so gives us $d(sigma,Id)=(n-1)+d(sigma',Id)+(n-1)=k$.

This completes the proof that any even value between $0$ and $leftlfloorfrac{1}{2}n^2rightrfloor$ is a distance between some pair of permutations.

Note that this chain of reasoning does not show that a value larger than $leftlfloorfrac{1}{2}n^2rightrfloor$ cannot be obtained by some permutation, nor that only even values are reachable; neither of which is too hard to prove.