Avoidance of Classical Patterns by Catalan Sequences

Abstract

A certain subset of the words of length $n$ over the alphabet of non-negative integers satisfying two restrictions has recently been shown to be enumerated by the Catalan number $C_{n-1}$. Members of this subset, which we will denote by $W(n)$, have been termed \emph{Catalan} \emph{words} or \emph{sequences} and are closely associated with the 321-avoiding permutations. Here, we consider the problem of enumerating the members of $W(n)$ satisfying various restrictions concerning the containment of certain prescribed subsequences or patterns. Among our results, we show that the generating function counting the members of $W(n)$ that avoid certain patterns is always rational for four general classes of patterns. Our proofs also provide a general method of computing the generating function for all the patterns in each of the four classes. Closed form expressions in the case of three-letter patterns follow from our general results in several cases. The remaining cases for patterns of length three, which we consider in the final section, may be done by various algebraic and combinatorial methods.