Distributions of mesh patterns of short lengths on king permutations

2024/11/27 by Dan Li, Li, Dan, Philip B. Zhang +1
Computer Science · Mathematics · #05A05 #05A15 #Advanced Combinatorial Mathematics #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2411.18131

openalex publication_date 2024/11/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Brändén and Claesson introduced the concept of mesh patterns in 2011, and since then, these patterns have attracted significant attention in the literature. Subsequently, in 2015, Hilmarsson et al. initiated the first systematic study of avoidance of mesh patterns, while Kitaev and Zhang conducted the first systematic study of the distribution of mesh patterns in 2019. A permutation σ= σ₁ σ₂ ⋯ σ_n in the symmetric group S_n is called a king permutation if | σ_i+1-σ_i | > 1 for each 1 ≤ i ≤ n-1. Riordan derived a recurrence relation for the number of such permutations in 1965. The generating function for king permutations was obtained by Flajolet and Sedgewick in 2009. In this paper, we initiate a systematic study of the distribution of mesh patterns on king permutations by finding distributions for 22 mesh patterns of short length.

Related

• Distributions of several infinite families of mesh patterns
• Distributions of mesh patterns of short lengths
• Quadrant marked mesh patterns in 132-avoiding permutations III
• Simple marked mesh patterns
• Mesh patterns and the expansion of permutation statistics as sums of permutation patterns