Lattice paths with a first return decomposition constrained by the maximal height of a pattern

Abstract

We consider the system of equations $A_k(x)=p(x)A_{k-1}(x)(q(x)+{\sum }_{i=0}^k{A}_i(x))$ for $k\ge r+1$ where $A_i(x)$, $0\le i\le r$, are some given functions and show how to obtain a close form for $A(x)={\sum }_{k\ge 0}{A}_k(x)$. We apply this general result to the enumeration of certain subsets of Dyck, Motzkin, skew Dyck, and skew Motzkin paths, defined recursively according to the first return decomposition with a monotonically non-increasing condition relative to the maximal ordinate reached by an occurrence of a given pattern $\pi$.

6 pages, 4 tables