Enumeration schemes for words avoiding patterns with repeated letters

Abstract In this paper, we discuss the enumeration of words avoiding patterns with repeated letters. More specifically, we find recurrences (i.e. enumeration schemes) counting words avoiding any pattern of length 3 and words avoiding any monotone pattern. Background The enumeration of permutation classes has been accomplished by many beautiful techniques. One natural extension of permutation classes is pattern-avoiding words. In [5], we adapted the method of enumeration schemes, first introduced for permutations by Zeilberger First, we recall the following definitions: n , w = w 1 · · · w n . The reduction of w, denoted red(w), is the unique word of length n obtained by replacing the i th smallest entries of w with i, for each i. Definition 2. Let w ∈ [k] n , w = w 1 · · · w n as above, and let q ∈ [k] m , q = q 1 · · · q m . We say that w contains q if there exist 1 ≤ i 1 < i 2 < · · · < i m ≤ n so that red(w i1 · · · w im ) = q. Otherwise w avoids q. For example, the reduction of w = 2432 ∈ While it is straightforward to fix a word w and list all the patterns q which it contains, it is a more difficult task to fix q and then enumerate the number of words w which do not contain q. To this end, we introduce our main object of study