Skip to main content
edited tags
Link
Source Link

Neighboring number of a permutation

For any positive integer $n\in\mathbb{N}$ let $S_n$ denote the set of all bijective maps $\pi:\{1,\ldots,n\}\to\{1,\ldots,n\}$. For $n>1$ and $\pi\in S_n$ define the neighboring number $N_n(\pi)$ as the minimum distance of $\pi$-neighbors, or more formally: $$N_n(\pi) = \min \big(\big\{|\pi(k)-\pi(k+1)|:k\in\{1,\ldots,n-1\}\big\}\cup \big\{|\pi(1) - \pi(n)|\big\}\big).$$

For $n>1$ let $E_n$ be the expected value of the neighboring number of a member of $S_n$.

Question. Do we have $\lim\sup_{n\to\infty}\frac{E_n}{n} > 0$?