Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers
share
The first problem addressed by this article is the enumeration of some families of pattern-avoiding inversion sequences. We solve some enumerative conjectures left open by the foundational work on the topics by Corteel et al., some of these being also solved independently by Kim and Lin. The strength of our approach is its robustness: we enumerate four families F_1 ⊂ F_2 ⊂ F_3 ⊂ F_4 of pattern-avoiding inversion sequences ordered by inclusion using the same approach. More precisely, we provide a generating tree (with associated succession rule) for each family F_i which generalizes the one for the family F_i-1. The second topic of the paper is the enumeration of a fifth family F_5 of pattern-avoiding inversion sequences (containing F_4). This enumeration is also solved via a succession rule, which however does not generalize the one for F_4. The associated enumeration sequence, which we call of powered Catalan numbers, is quite intringuing, and further investigated. We provide two different succession rules for it, denoted Ω_pCat and Ω_steady, and show that they define two types of families enumerated by powered Catalan numbers. Among such families, we introduce the steady paths, which are naturally associated with Ω_steady. They allow to brigde the gap between the two types of families enumerated by powered Catalan numbers: indeed, we provide a size-preserving bijection between steady paths and valley-marked Dyck paths (which are naturally associated to Ω_pCat). Along the way, we provide several nice connections to families of permutations defined by the avoidance of vincular patterns, and some enumerative conjectures.
READ FULL TEXT