How permutations displace points and stretch intervals

Abstract

Let $S_n$ be the set of permutations on $\{1,\dots ,n\}$ and $\pi \in S_n$. Let $\mathrm{d}(\pi )$ be the arithmetic average of $\{|i-\pi (i)|;1\le i\le n\}$. Then $\mathrm{d}(\pi )/n\in [0,1/2]$, the expected value of $\mathrm{d}(\pi )/n$ approaches $1/3$ as $n$ approaches infinity, and $\mathrm{d}(\pi )/n$ is close to $1/3$ for most permutations. We describe all permutations $\pi$ with maximal $\mathrm{d}(\pi )$. Let ${\mathrm{s}}^{+}(\pi )$ and ${\mathrm{s}}^{\ast }(\pi )$ be the arithmetic and geometric averages of $\{|\pi (i)-\pi (i+1)|;1\le i<n\}$, and let $M^{+}$, $M^{\ast }$ be the maxima of ${\mathrm{s}}^{+}$ and ${\mathrm{s}}^{\ast }$ over $S_n$, respectively. Then $M^{+}=(2m^2-1)/(2m-1)$ when $n=2m$, $M^{+}=(2m^2+2m-1)/(2m)$ when $n=2m+1$, $M^{\ast }=(m^m(m+1{)}^{m-1}{)}^{1/(n-1)}$ when $n=2m$, and, interestingly, $M^{\ast }=(m^m(m+1)(m+2{)}^{m-1}{)}^{1/(n-1)}$ when $n=2m+1>1$. We describe all permutations $\pi$, $\sigma$ with maximal ${\mathrm{s}}^{+}(\pi )$ and ${\mathrm{s}}^{\ast }(\sigma )$.