2007/12/21 by Toufik Mansour, Yidong Sun · 29 citations
Agricultural and Biological Sciences · Mathematics · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Algorithm #Botanical Research and Chemistry #Catalan number #Combinatorial proof #Combinatorics #Computer science #Discrete mathematics #Generating function #Integer lattice #Mathematics #Path (computing) #math.CO #msc:05A05 #msc:05A15
paper · pdf · doi:10.1016/j.dam.2007.10.009
published in Discrete Applied Mathematics 156(12), 2279-2292 (Elsevier BV) · 15pages, 1 figure. To appear in Discrete Applied Mathematics
openalex publication_date 2007/12/21 · arxiv created 2008/05/09 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
A \em k-generalized Dyck path of length n is a lattice path from (0,0) to (n,0) in the plane integer lattice ℤ×ℤ consisting of horizontal-steps (k, 0) for a given integer k≥ 0, up-steps (1,1), and down-steps (1,-1), which never passes below the x-axis. The present paper studies three kinds of statistics on k-generalized Dyck paths: "number of u-segments", "number of internal u-segments" and "number of (u,h)-segments". The Lagrange inversion formula is used to represent the generating function for the number of k-generalized Dyck paths according to the statistics as a sum of the partial Bell polynomials or the potential polynomials. Many important special cases are considered leading to several surprising observations. Moreover, enumeration results related to u-segments and (u,h)-segments are also established, which produce many new combinatorial identities, and specially, two new expressions for Catalan numbers.