2013/03/11 by Axel Bacher, Bacher, Axel
Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology #Mathematics and Applications
paper · pdf · doi:10.48550/arxiv.1303.2724
openalex publication_date 2013/03/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Generalized Dyck paths (or discrete excursions) are one-dimensional paths that take their steps in a given finite set S, start and end at height 0, and remain at a non-negative height. Bousquet-Mélou showed that the generating function Ek of excursions of height at most k is of the form Fk/Fk+1, where the Fk are polynomials satisfying a linear recurrence relation. We give a combinatorial interpretation of the polynomials Fk and of their recurrence relation using a transfer matrix method. We then extend our method to enumerate discrete meanders (or paths that start at 0 and remain at a non-negative height, but may end anywhere). Finally, we study the particular case where the set S is symmetric and show that several simplifications occur.