Patterns in rectangulations. Part I: $\top$-like patterns, inversion sequence classes $I(010, 101, 120, 201)$ and $I(011, 201)$, and rushed Dyck paths
We initiate a systematic study of pattern avoidance in rectangulations. We give a formal definition of such patterns and investigate rectangulations that avoid $\top$-like patterns - the pattern $\top$ and its rotations. For every $L \subseteq \{\top, \, \vdash, \, \bot, \, \dashv \}$ we enumerate $L$-avoiding rectangulations, both weak and strong. In particular, we show $\top$-avoiding weak rectangulations are enumerated by Catalan numbers and construct bijections to several Catalan structures. Then, we prove that $\top$-avoiding strong rectangulations are in bijection with several classes of inversion sequences, among them $I(010,101,120,201)$ and $I(011,201)$ - which leads to a solution of the conjecture that these classes are Wilf-equivalent. Finally, we show that $\{\top, \bot\}$-avoiding strong rectangulations are in bijection with recently introduced rushed Dyck paths. 30 pages, 21 figures
Authors
- Andrei Asinowski (ORCID: https://orcid.org/0000-0002-0689-0775)
- Michaela A. Polley
Publication Details
- Journal
- Discrete Mathematics & Theoretical Computer Science
- Published
- 2025-10-16
- DOI
- https://doi.org/10.46298/dmtcs.15118
- Primary Topic
- Computational Geometry and Mesh Generation
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Austrian Science Fund