Ascent Sequences Avoiding a Triple of Length-3 Patterns

Abstract

An ascent sequence is a sequence $a_1a_2\cdots a_n$ consisting of non-negative integers satisfying $a_1=0$ and for $1<i\leq n$, $a_i\leq \text{asc}(a_1a_2\cdots a_{i-1})+1$, where $\text{asc}(a_1a_2\cdots a_k)$ is the number of ascents in the sequence $a_1a_2\cdots a_k$. We say that two sets of patterns $B$ and $C$ are $A$-Wilf-equivalent if the number of ascent sequences of length $n$ that avoid $B$ equals the number of ascent sequences of length $n$ that avoid $C$, for all $n\geq0$. In this paper, we show that the number of $A$-Wilf-equivalences among triples of length-3 patterns is 62. The main tool is generating trees; bijective methods are also sometimes used. One case is of particular interest: ascent sequences avoiding the 3 patterns 100, 201 and 210 are easy to characterize, but it seems remarkably involved to show that, like 021-avoiding ascent sequences, they are counted by the Catalan numbers.