Permutations, Pattern Covers, Posets and Positivity: Part I: Patterns and Posets
Abstract
We study permutations covered by overlapping occurrences of a consecutive pattern. Special cases of this have been studied for consecutive patterns and via the cluster method. We study enumeration sequences obtained by repeating a fixed overlap. We elicit many structural properties of such pattern covers, mainly in terms of posets whose linear extensions are in bijection with the permutations in question. The enumeration of these permutations for different patterns gives rise to a great variety of sequences, many classical, but most of them not found in the OEIS. We conjecture that, essentially, all these sequences are moments of probability measures on the real line. We develop an enumerative and order-theoretic framework for this. For overlap 1 we give a generating function whose coefficients enumerate permutations covered by any fixed pattern with any fixed number of occurrences. For overlap at most half the pattern length we derive a polynomial-time enumeration formula. We associate to each pattern, overlap, and number of occurrences a poset whose linear extensions are the corresponding permutations. The regularity of this poset construction makes possible a structural analysis that in many cases leads to enumerative formulas for large classes of patterns. We prove uniform restrictions on the local structure of the Hasse diagrams, describe their branches (pendant chains) in terms of the corresponding patterns, and characterize when the poset is a tree or chain or subdivisions of a grid. Some of these constructions yield explicit families of formulas and explain unexpected equinumerations. In a forthcoming paper we investigate the sequences arising here from a probabilistic perspective, viewing them both as point processes and as moment sequences. We also obtain integral and matrix representations for important overlap 1 and 2 classes of pattern-covering sequences.
Related
- q-Zeta positivity for root and Ferrers-cell posets
- Pattern avoidance classes of parking permutations with fixed lucky sets
- Staircase diagrams, pattern avoidance, and smooth permutations
- The Distribution of Double Deficiencies in Pattern-Avoiding Permutations
- Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231
BibTeX
@misc{blitvic2026permutations,
title = {{Permutations, Pattern Covers, Posets and Positivity: Part I: Patterns and Posets}},
author = {Natasha Blitvić and Mohammed Slim Kammoun and Einar Steingrímsson},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29846},
eprint = {2610.29846},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29846},
}
RIS
TY - UNPB
TI - Permutations, Pattern Covers, Posets and Positivity: Part I: Patterns and Posets
AU - Natasha Blitvić
AU - Mohammed Slim Kammoun
AU - Einar Steingrímsson
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29846
UR - https://arxiv.org/abs/2610.29846
AB - We study permutations covered by overlapping occurrences of a consecutive pattern. Special cases of this have been studied for consecutive patterns and via the cluster method. We study enumeration sequences obtained by repeating a fixed overlap. We elicit many structural properties of such pattern covers, mainly in terms of posets whose linear extensions are in bijection with the permutations in question. The enumeration of these permutations for different patterns gives rise to a great variety of sequences, many classical, but most of them not found in the OEIS. We conjecture that, essentially, all these sequences are moments of probability measures on the real line. We develop an enumerative and order-theoretic framework for this. For overlap 1 we give a generating function whose coefficients enumerate permutations covered by any fixed pattern with any fixed number of occurrences. For overlap at most half the pattern length we derive a polynomial-time enumeration formula. We associate to each pattern, overlap, and number of occurrences a poset whose linear extensions are the corresponding permutations. The regularity of this poset construction makes possible a structural analysis that in many cases leads to enumerative formulas for large classes of patterns. We prove uniform restrictions on the local structure of the Hasse diagrams, describe their branches (pendant chains) in terms of the corresponding patterns, and characterize when the poset is a tree or chain or subdivisions of a grid. Some of these constructions yield explicit families of formulas and explain unexpected equinumerations. In a forthcoming paper we investigate the sequences arising here from a probabilistic perspective, viewing them both as point processes and as moment sequences. We also obtain integral and matrix representations for important overlap 1 and 2 classes of pattern-covering sequences.
ER -