Completing the enumeration of inversion sequences avoiding one or two patterns of length 3
arXiv:2407.07701 · doi:10.37236/13750
Abstract
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.
Supersedes arXiv:2212.07222. 58 pages, 5 figures, 3 tables