Generalized Dyck paths (Q757416): Difference between revisions

Let \({\mathcal S}\) be a finite multi-set (a set with repetitions) of vectors in \({\mathbb{N}}\times {\mathbb{N}}\) and let \({\mathcal S}^*=\{(r,-s)+(r,s)\in {\mathcal S}\}.\) An A-path (\({\mathcal S}\)-Dyck path) is a path in \({\mathbb{Z}}\times {\mathbb{Z}}\) which starts from (0,0) and ends on the x-axis, uses only vectors from \({\mathcal S}+{\mathcal S}^*\) and never goes below the x-axis. The author defines five other related types of paths. Each type gives rise to a generating function of several variables. These functions satisfy a system of equations which yield a polynomial equation satisfied by \textbf{A}, the generating function for A-paths. For example, when \({\mathcal S}=\{{\mathbf{u}}_ 1,{\mathbf{u}}_ 2\}\) where \textbf{u}\({}_ 1=(r_ 1,1)\), \textbf{u}\({}_ 2=(r_ 2,2)\). A satisfies a 4th degree polynomial equation.