King permutations and partially ordered patterns

Tools

Li, Dan and Kitaev, Sergey (2026) King permutations and partially ordered patterns. Integers: Electronic Journal of Combinatorial Number Theory, 26. A59. ISSN 1553-1732 (https://doi.org/10.5281/zenodo.19949822)

[thumbnail of Li-Kitaev-Integers-2026-King-permutations-and-partially-ordered-patterns]
Preview
 Text. Filename: Li-Kitaev-Integers-2026-King-permutations-and-partially-ordered-patterns.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (444kB)| Preview

Abstract

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.

ORCID iDs

Li, Dan and Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647;
CORE (COnnecting REpositories)