King Permutations and Partially Ordered Patterns

Finding distributions of statistics in pattern-avoiding permutations has attracted significant attention in the literature. In particular, partially ordered patterns (POPs) have been extensively studied in various contexts. In this paper, we extend the study of POPs to the domain of king permutations, introduced by Riordan in 1965 and later explored in a series of papers. A permutation σ1σ2 · · · σn is called a king permutation if |σi+1 − σi | > 1 for each 1 ≤ i ≤ n − 1. As the main results of this paper, we derive closed-form expressions for the generating functions that simultaneously account for four permutation statistics: ascents, descents, left-to-right maxima (or left-to-right minima), and right-to-left maxima (or right-to-left minima), on king permutations avoiding any flat POP of size 4. As a special case, we provide distributions of descents over length-4 flat POP-avoiding king permutations. Moreover, we discuss several restrictions that result in the non-existence of king permutations satisfying them. In particular, we note that no separable king permutations exist.