Generalized Dyck paths
type: Item
instance of: scholarly article
title: Generalized Dyck paths
zbMATH Open document ID: 0723.05074
DOI: 10.1016/0012-365X(90)90039-K
author: Jacques Labelle
author: Yeong-Nan Yeh
published in: Discrete Mathematics
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4191703
zbMATH Keywords: Dyck path
zbMATH Keywords: Catalan number
zbMATH Keywords: generating function
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: Q4096964
cites work: Q5625162
cites work: Q3669422
cites work: Dyck paths of knight moves
cites work: Q3748279
cites work: Q3726126
cites work: Q3469384
full work available at URL: 0012-365x(90)90039-k
OpenAlex ID: W1966578568
description: scientific article; zbMATH DE number 4191703