Counting words avoiding patterns of length three with generating functions

Sammanfattning: The set of 123-avoiding words with exactly r occurrences of each letter was recently enumerated by N. Shar and D. Zeilberger. This paper enumerates more complicated sets of pattern avoiding words, such as those allowing 1, 2, ... or r occurrences of each letter, or those for which the numbers of occurrences of each individual letter follow a repeating sequence. The results are also generalized to apply to all patterns of length three with distinct letters. The generating functions enumerating the words are shown to be algebraic, for all investigated sets of words. A notable number of coefficients for the relevant generating functions have been found and the first few confirmed by independent methods. The asymptotic behaviour of these coefficients has been established as exponential. The employed strategy involves partitioning words into subwords which allow for the construction of equations relating the generating functions.