Consecutive patterns in Catalan words and the descent distribution (Q6133614)

This paper studies the descent statistic in Catalan words avoiding a consecutive pattern of length \(3\). A Catalan word is a word \(w = w_1w_2\cdots w_n\) over the set of nonnegative integers with \(w_1 = 0\) and \(w_{i} \leq w_{i-1} + 1\) for all \(i \geq 2\). It is well known that the number of Catalan words of length \(n\) is the Catalan number \(\frac{1}{n+1}\binom{2n}{n}\). A Catalan word \(w\) is said to avoid a consecutive pattern \(p = \underline{p_1p_2\cdots p_k}\) if there is no consecutive subsequence \(w_iw_{i+1} \cdots w_{i+k-1}\) that is order-isomorphic to \(p\). Every Catalan word avoids \(\underline{021}\) and \(\underline{102}\) by definition, leaving eleven possible consecutive patterns of length \(3\) for which enumerating Catalan words avoiding the pattern is meaningful. In each of these cases, the authors determine a bivariate generating function for Catalan words avoiding the pattern, with the second variable marking the number of descents. From this, they also derive the generating function for the total number of descents in each case. As it turns out, the patterns \(\underline{001}\) and \(\underline{011}\) lead to the same generating function, as do the three patterns \(\underline{100},\underline{110}\) and \(\underline{120}\). Thus there are only eight distinct bivariate generating functions that occur.