Counting subword patterns in Catalan words

Let An denote the set of integral sequences w = w1⋯wn such that wi + 1 ≤ wi + 1 for 1 ≤ i ≤ n − 1, with w1 = 1. In this paper, we enumerate the members of An, known as Catalan words, according to the number of occurrences of any subword pattern of length two or three. In particular, we find an explicit formula for the generating function of the distribution on An of each pattern. We obtain these formulas as specific cases of more general results involving multivariate distributions involving two or more patterns and the last letter statistic on An. To prove these results, we make use of the kernel method to solve functional equations satisfied by the relevant generating functions. Differentiating the generating function formulas, we obtain simple explicit expressions for the total number of occurrences of each pattern on An. These expressions may subsequently be explained combinatorially using correspondences with various types of lattice paths.