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 $d(\pi )$ be the arithmetic average of $\{|i–\pi (i)|:1\le i\le n\}$. Then $d(\pi )/n\in [0,1/2]$, the expected value of $d(\pi )/n$ approaches $1/3$ as $n$ approaches infinity, and $d(\pi )/n$ is close to $1/3$ for most permutations. We describe all permutations $\pi$ with maximal $d(\pi )$.

Let $s^{+}(\pi )$ and $s^{\ast }(\pi )$ be the arithmetic and geometric averages of $\{|\pi (i)–\pi (i+1)|:1\le i1$. We describe all permutations $\pi$,$\sigma$ with maximal $s^{+}(\pi )$ and $s^{\ast }(\sigma )$.