Distributions of mesh patterns of short lengths on king permutations

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 \emph{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 $\sigma ={\sigma }_1{\sigma }_2\cdots {\sigma }_n$ in the symmetric group $S_n$ is called a king permutation if $\left|{\sigma }_{i+1}-{\sigma }_i\right|>1$ for each $1\le i\le 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.

arXiv comment26 pages