zbMATH — the first resource for mathematics

Generalized Dyck paths. (English) Zbl 0723.05074
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 A, the generating function for A-paths. For example, when \({\mathcal S}=\{{\mathbf{u}}_ 1,{\mathbf{u}}_ 2\}\) where u\({}_ 1=(r_ 1,1)\), u\({}_ 2=(r_ 2,2)\). A satisfies a 4th degree polynomial equation.

05C38 Paths and cycles
Full Text: DOI
[1] Berge, C., Graphes et hypergraphes, (1973), Dunod · Zbl 0332.05101
[2] Comtet, L., Analyse combinatoire, (1970), Presses Universitaires de France, SUP · Zbl 0221.05001
[3] Goulden, I.P.; Jackson, D.M., Combinatorial enumeration, (1983), John Wiley and Sons · Zbl 0519.05001
[4] A. Kotzig and J. Labelle, Sur les graphes de mouvements de cavaliers généralisés, Centre de Recherche en Mathématiques, Univ. de Montréal, Rapport no. 1460.
[5] Kraitchik, M., Recreationnal mathematics, (1942), Dover
[6] Kreweras, G., Combinatoire énumérative des ponts de Catalan (ou mots de Dyck), Talk at UQAM, (April 16th 1987)
[7] Labelle, J., Théorie des graphes, (1981), Modulo Editeur
[8] Labelle, J.; Yeh, Y.N., Dyck paths of knight moves, Discrete appl. math., 24, 213-221, (1989) · Zbl 0691.05004
[9] Stanley, R., Enumerative combinatorics, Vol. 1, (1986), Addison-Wesley · Zbl 0608.05001
[10] Stanton, D.; White, D., Constructive combinatorics, (1986), U.T.M., Springer Verlag · Zbl 0595.05002
[11] Viennot, G.X., Théorie combinatoire des nombres d’Euler et de Genocchi, (), année · Zbl 0694.34009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.