How permutations displace points and stretch intervals.

MaRDI QIDQ3073557zbMATH OpenFDO

Authors Daniel Daly, Petr Vojtěchovský

Publication date 11 February 2011

Full work available at URL https://arxiv.org/abs/1509.05649

zbMATH Keywords

displacementlong jumppermutationstretch

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Abstract: Let $S_n$ be the set of permutations on $1,,dots,,n$ and $piin{S}_n$. Let $mathrmd(pi)$ be the arithmetic average of $|i-pi(i)|;;1leilen$. Then $mathrmd(pi)/nin[0,,1/2]$, the expected value of $mathrmd(pi)/n$ approaches $1/3$ as $n$ approaches infinity, and $mathrmd(pi)/n$ is close to $1/3$ for most permutations. We describe all permutations $pi$ with maximal $mathrmd(pi)$. Let $mathrm{s}^{+}(pi)$ and $mathrm{s}^{\ast }(pi)$ be the arithmetic and geometric averages of $|pi(i)-pi(i+1)|;;1lei<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)$.

Recommendations

• The minimum Manhattan distance and minimum jump of permutations
• On the maximum number of permutations with given maximal or minimal distance
• The average order of a permutation
• The number of permutations with a given signature, and the expectations of their elements
• On the number of permutations on n objects with greatest cycle length k

Cited in

(7)

• On the average discrepancy of successive tuples of pseudo-random numbers over parts of the period
• Permutations in two dimensions that maximally separate neighbors
• On summing permutations and some statistical properties
• scientific article; zbMATH DE number 3882432 (Why is no real title available?)
• A study of total relative displacements of permutations in paths and cycles
• Sós permutations
• Lengths of tours and permutations on a vertex set of a convex polygon.

This page was built for publication: How permutations displace points and stretch intervals.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3073557)