Metric $d(\sigma,\tau)$ in $S_{n}$ 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, \tau\in S_{n}$, such that $$d(\sigma,\tau)=\sum_{i=1}^{n}\vert\sigma(i)-\tau(i)\vert$$. What are the values of $d(\sigma,\tau)$ can be?
Any ideas from which point should I start?
 A: 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.
A: The value of $d(\sigma,\tau)$ can be any even integer between $0$ and $\left\lfloor\frac{1}{2}n^2\right\rfloor$. 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 $n\leq 2$, the problem is trivial. From now on, we'll assume $n\geq 3$.

*If $k < 2(n-1)$, we can deduce that $k\leq 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 & \left\lfloor\frac{1}{2}(n-1)^2\right\rfloor \\
\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 $k\geq 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 & \left\lfloor \frac{1}{2}n^2\right\rfloor - 2(n-1)\\
& = & \left\lfloor \frac{1}{2}\left(n^2 - 4n + 4\right)\right\rfloor\\
& = & \left\lfloor \frac{1}{2}\left(n-2\right)^2\right\rfloor
\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 $\left\lfloor\frac{1}{2}n^2\right\rfloor$ is a distance between some pair of permutations.
Note that this chain of reasoning does not show that a value larger than $\left\lfloor\frac{1}{2}n^2\right\rfloor$ cannot be obtained by some permutation, nor that only even values are reachable; neither of which is too hard to prove.
