Ascent sequences avoiding a triple of length-3 patterns

David Callan ; Toufik Mansour¹

¹University of Haifa

The electronic journal of combinatorics, Tome 32 (2025) no. 1

Résumé

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.

Détail

DOI : 10.37236/12720

Classification : 05A05, 05A15, 11B75, 11B83
Mots-clés : \(A\)-Wilf-equivalent sets