HOW PERMUTATIONS DISPLACE POINTS AND STRETCH INTERVALS

Abstract. For pi ∈ Sn, let d(pi) be the arithmetic average of {|i − pi(i)|; 1 ≤ i ≤ n}. Then 0 ≤ d(pi)/n ≤ 1/2, the expected value of d(pi)/n approaches 1/3 as n approaches infinity, and most permutations have d(pi)/n close to 1/3. We also describe all permutations with d(pi)/n = 1/2. Let s+(pi) and s∗(pi) be the arithmetic and geometric averages of {|pi(i) − pi(i + 1)|; 1 ≤ i < n}, respectively. Let M+, M ∗ be the maxima of s+ and s ∗ over Sn, respectively. Then M+ = (2m2 − 1)/(2m − 1) when n = 2m, M+ = (2m2 + 2m − 1)/(2m) when n = 2m + 1, M ∗ = (mm(m + 1)m−1)1/(n−1) when n = 2m, and M ∗ = (mm(m + 1)(m + 2)m−1)1/(n−1) when n = 2m + 1> 1. We also describe all permutations pi, σ with s+(pi) =M+, s∗(σ) =M∗. 1. Motivation an