Completing the Enumeration of Inversion Sequences Avoiding One or Two Patterns of Length $3$
We present four constructions of inversion sequences, and use them to compute the enumeration sequences of 24 classes of pattern-avoiding inversion sequences. This completes the enumeration of inversion sequences avoiding one or two patterns of length 3. Some of our constructions are based on generating trees. Others involve pattern-avoiding words, which we also count using generating trees. To solve some of these cases, we introduce a generalization of inversion sequences, which we call shifted inversion sequences. Lastly, we briefly discuss the asymptotics of pattern-avoiding inversion sequences, focusing on their exponential or super-exponential behavior.
Authors
- Benjamin Testart
Institutions
- Université de Lorraine (FR)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2025-11-13
- DOI
- https://doi.org/10.37236/13750
- Primary Topic
- semigroups and automata theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00