Patterns in Random Permutations Avoiding the Pattern 132

2014/01/22 by Svante Janson · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithm #Bayesian Methods and Mixture Models #Brownian excursion #Brownian motion #Combinatorics #Computer science #Derangement #Discrete mathematics #Excursion #Geometric Brownian motion #Geometry #Limit (mathematics) #Mathematical analysis #Mathematics #Permutation (music) #Physics #Random permutation #Recursion (computer science) #Scaling #Scaling limit #Set (abstract data type) #Statistics #Stochastic processes and statistical mechanics #Symmetric group #math.CO #math.PR #msc:05A05 #msc:60C05 #msc:60F05

paper · pdf · doi:10.1017/s0963548316000171

32 pages

arxiv created 2014/01/22 · openalex publication_date 2016/05/18 · arxiv updated 2016/05/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We consider a random permutation drawn from the set of 132-avoiding permutations of length n and show that the number of occurrences of another pattern σ has a limit distribution, after scaling by n λ (σ)/2 , where λ(σ) is the length of σ plus the number of descents. The limit is not normal, and can be expressed as a functional of a Brownian excursion. Moments can be found by recursion.

Citations

• Some Combinatorial Properties of Schubert Polynomials
• Continuous Martingales and Brownian Motion
• The enumeration of permutations avoiding 2143 and 4231
• Bijections from Dyck paths to 321-avoiding permutations revisited
• The copies of any permutation pattern are asymptotically normal
• Foundations of Modern Probability
• On q-functional equations and excursion moments
• Restricted Permutations

Cited by

• Square permutations are typically rectangular