2
$\begingroup$

I am interested in references to results on permutations $\sigma$ of $\{0,\ldots,n-1\}$ satisfying $\text{min}\{ \sigma(i)-i\text{ (mod } n),i-\sigma(i) \text{ (mod } n) \} \leq k$ for some $k$ for all $i$. I don't know if there is a common term for these, so I settled for the "bounded displacement" in the title.

I was only able to find two related topics, but both with the linear order, without the "mod $n$" part. These are the band permutations and probabilistic results about them, concerned with random walks (and relaxing the "all $i$" assumption to just "most $i$"), discussed in this video, and the enumeration problem for permutations with bounded drop (bounding the value of $i-\sigma(i)$ instead) inspired by sorting problems, and solved in this paper. It also seems like such permutations might arise with Schreier graphs, but I was unable to find any references, nor analogues of the previous two on the circle.

I am not primarily concerned with counting these permutations (but will be happy to see that too). Ideally, I would like to see dynamical results about such a permutation of a discrete set, or about quantities invariant or bounded under such permutation acting on $\mathbb{R}^n$, since this is the context we encountered them in.

Improve this question
$\endgroup$
3
  • $\begingroup$ Given the last paragraph, arxiv.org/abs/1301.4736 might be related. $\endgroup$
    – Ville Salo
    Commented Jul 20, 2020 at 21:23
  • $\begingroup$ Let $f_k(n)$ be the number of such permutations. By the technique used to prove Proposition 4.7.10 of Enumerative Combinatorics, vol. 1, second ed., if we interpret $f_k(n)$ suitably for small $n$ then $\sum_{n\geq 0}f_k(n)x^n=-xQ_k'(x)/Q_k(x)$ for some polynomial $Q_k(x)$. $\endgroup$
    – Richard Stanley
    Commented Jul 20, 2020 at 22:32
  • $\begingroup$ It would be great if you could add this to findstat.org. (I'm on a cellphone right now) here is code: def statistic(pi): n=len(pi) return max(min((e-1-i)%n,(i-e+1)%n) for i,e in enumeate(pi)) $\endgroup$
    – Martin Rubey
    Commented Jul 21, 2020 at 7:07

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .