How permutations displace points and stretch intervals

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

No reviews yet.

No comments yet.