The Expected Number of Distinct Consecutive Patterns in a Random Permutation

2020/11/24 by Austin Allen, Allen, Austin, Dylan Cruz Fonseca +15
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #05A05 #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Genome Rearrangement Algorithms #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2011.12179

openalex publication_date 2020/11/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let π_n be a uniformly chosen random permutation on [n]. Using an analysis of the probability that two overlapping consecutive k-permutations are order isomorphic, we show that the expected number of distinct consecutive patterns in π_n is (n²)/(2)(1-o(1)). This exhibits the fact that random permutations pack consecutive patterns near-perfectly.

Related

• Emerging consecutive pattern avoidance
• A probabilistic approach to consecutive pattern avoiding in permutations
• A survey of consecutive patterns in permutations
• Counting Consecutive Pattern Matches in S_n(132) and S_n(123)
• Symmetric and Asymptotically Symmetric Permutations