Wilf Classes for Level Sequences Avoiding Patterns of Length Three

A level sequence is a word π=π1π2…πn over the set of nonnegative integers such that π1=0 and πi≤1+lev(π1π2…πi−1) for i=2,3,…,n, where lev(π1π2…πm) is the number of levels in the word π1π2…πm, that is, the number of two entry factors πjπj+1 such that πj=πj+1. In this paper, we obtain some enumerative results for level sequences avoiding patterns of length 3. In particular, we determine the number of Wilf equivalence classes among single patterns of length 3 and among pairs of patterns of length 3, and state the corresponding result for a set of k patterns of length 3 when 3≤k≤13.