The minimum Manhattan distance and minimum jump of permutations

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:161

Article

Blackburn, Simon R.¹  Bomberger, Cheyne²  Winkler, Peter³ 

[1] Royal Holloway Univ London, Dept Math, Egham TW20 0EX, Surrey, England

[2] Univ Maryland, Dept Math & Stat, Baltimore, MD 21250 USA

[3] Dartmouth, Dept Math, Hanover, NH 03755 USA

关键词: Permutations;    Asymptotic enumeration;    Manhattan distance;   

DOI  :  10.1016/j.jcta.2018.09.002

来源: Elsevier

【 摘 要 】

Let pi be a permutation of {1, 2, ... , n}. If we identify a permutation with its graph, namely the set of n dots at positions (i, pi(i)), it is natural to consider the minimum L-1 (Manhattan) distance, d(pi), between any pair of dots. The paper computes the expected value (and higher moments) of d(pi) when n -> infinity and pi it is chosen uniformly, and settles a conjecture of Bevan, Bomberger and Tenner (motivated by permutation patterns), showing that when d is fixed and n -> infinity, the probability that d(pi) >= d + 2 tends to e(-d2-d). The minimum jump mj(pi) of pi, defined by mj(pi) = min(1 <= i <= n-1) vertical bar pi(i + 1) - pi(i)vertical bar, is another natural measure in this context. The paper computes the asymptotic moments of mj(pi), and the asymptotic probability that mj(pi) >= d + 1 for any constant d. (C) 2018 Elsevier Inc. All rights reserved.

【 授权许可】

Free