Wilf classes for descent sequences avoiding a pattern or a pair of patterns of length three

Abstract

A descent sequence is a word $\pi=\pi_1\pi_2\cdots\pi_n$ over the set of nonnegative integers such that $\pi_1=0$ and $\pi_i\leq1+\des(\pi_1\pi_2\cdots\pi_{i-1})$ for $i=2,3,\ldots,n$, where $\des(\pi_1\pi_2\cdots\pi_m)$ is the number of descents in the word $\pi_1\pi_2\cdots\pi_m$, that is, the number of two entry factors $\pi_j\pi_{j+1}$ such that $\pi_j>\pi_{j+1}$. In this paper, we obtain some enumerative results for descent sequences avoiding patterns of length three and four. In particular, we determine the number of Wilf equivalence classes among single patterns of length three and among pairs of patterns of length 3, and state the corresponding result for a set of $k$ patterns of length 3 when $3\le k \le 13$. We also consider single patterns of length 4. The main tool is the use of generating trees.