How Permutations Displace Points and Stretch Intervals

Abstract

Let \(S_n\) be the set of permutations on \(\{1, \ldots, n\}\) and \(\pi \in S_n\). Let \(d(\pi)\) be the arithmetic average of \(\{|i – \pi(i)| : 1 \leq i \leq 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^*(\pi)\) be the arithmetic and geometric averages of \(\{|\pi(i) – \pi(i + 1)| : 1 \leq i 1\). We describe all permutations \(\pi\),\(\sigma\) with maximal \(s^+(\pi)\) and \(s^*(\sigma)\).