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

We introduce an algorithmic approach based on a generating tree method for enumerating the inversion sequences with var-ious pattern-avoidance restrictions. For a given set of patterns, we propose an algorithm that outputs either an accurate de-scription of the succession rules of the corresponding generat-ing tree or an ansatz. By using this approach, we determine the generating trees for the pattern classes In(000, 021), In(100, 021), In(110, 021), In(102, 021), In(100, 012), In(011, 201), In(011, 210) and In(120, 210). Then we use the kernel method, obtain generat-ing 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. Moreover, we extend the algorithm to restricted growth sequences and apply it to several classes. In particular, we present explicit formulas for the generat-ing functions of the restricted growth sequences that avoid either {12313, 12323}, {12313, 12323, 12333}, or {123 center dot center dot center dot B1}.(c) 2023 Elsevier Ltd. All rights reserved.

Automated summary

We introduce an algorithmic approach based on a generating tree method for enumerating the inversion sequences with various pattern-avoidance restrictions. The algorithm outputs either an accurate description of the succession rules of the generating tree or an ansatz for a given set of patterns. We determine the generating trees for several pattern classes and obtain generating functions and enumerating formulas using the kernel method.