Abstract
A partial order ≺ on [n] is naturally labelled (NL) if x ≺ y implies x < y. We establish a bijection between {3, 2+2}-free NL posets and 12–34-avoiding permutations, determine functional equations satisfied by their generating function, and use series analysis to investigate their asymptotic growth, presenting evidence of stretched exponential behaviour. We also exhibit bijections between 3-free NL posets and various other objects, and determine their generating function. The connection between our results and a hierarchy of combinatorial objects related to interval orders is described.
Original language | English |
---|---|
Article number | 104117 |
Number of pages | 18 |
Journal | European Journal of Combinatorics |
Volume | 126 |
Early online date | 13 Jan 2025 |
DOIs | |
Publication status | E-pub ahead of print - 13 Jan 2025 |
Keywords
- naturally labelled poset
- pattern avoidance
- bijective combinatorics
- generating function
- asymptotic series analysis
- stretched exponential