An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences

Abstract

We introduce an algorithmic approach based on generating tree method for enumerating the inversion sequences with various pattern-avoidance restrictions. For a given set of patterns, we propose an algorithm that outputs either an accurate description of the succession rules of the corresponding generating tree or an ansatz. By using this approach, we determine the generating trees for the pattern-classes $I_n(000,021),I_n(100,021)$, $I_n(110,021),I_n(102,021)$, $I_n(100,012)$, $I_n(011,201)$, $I_n(011,210)$ and $I_n(120,210)$. Then we use the kernel method, obtain generating functions of each class, and find enumerating formulas. Lin and Yan studied the classification of the Wilf-equivalences for inversion sequences avoiding pairs of length-three patterns and showed that there are 48 Wilf classes among 78 pairs. In this paper, we solve six open cases for such pattern classes.

arXiv comment20 pages, 2 figures. Section 5 added. Typos in Equation 4.16 and Theorem 4.4 corrected. The authors thank Jay Pantone for pointing out them

References in corpus (5)

• Patterns in Inversion Sequences I
• Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations
• Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers
• Inversion sequences avoiding pairs of patterns
• Length-Four Pattern Avoidance in Inversion Sequences