Fibonacci and Catalan paths in a wall

被引:0
作者
Baril, Jean-Luc [1 ]
Ramirez, Jose L. [2 ]
机构
[1] Univ Bourgogne Franche Comte, LIB, BP 47 870, F-21078 Dijon, France
[2] Univ Nacl Colombia, Dept Matemat, Bogota, Colombia
关键词
Catalan; Fibonacci; Dyck path; Generating function; Kernel method; DYCK PATHS;
D O I
10.1016/j.disc.2024.114268
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We study the distribution of some statistics (width, number of steps, length, area) defined for paths contained in walls. We present the results by giving generating functions, asymptotic approximations, as well as some closed formulas. We prove algebraically that paths in walls of a given width and ending on the x-axis are enumerated by the Catalan numbers, and we provide a bijection between these paths and Dyck paths. We also find that paths in walls with a given number of steps are enumerated by the Fibonacci numbers. Finally, we give a constructive bijection between the paths in walls of a given length and peakless Motzkin paths of the same length.
引用
收藏
页数:14
相关论文
共 28 条
  • [1] Asinowski A., 2020, Semin. Lothar. Comb, V84
  • [2] Basic analytic combinatorics of directed lattice paths
    Banderier, C
    Flajolet, P
    [J]. THEORETICAL COMPUTER SCIENCE, 2002, 281 (1-2) : 37 - 80
  • [3] Generating functions for generating trees
    Banderier, C
    Bousquet-Mélou, M
    Denise, A
    Flajolet, P
    Gardy, D
    Gouyou-Beauchamps, D
    [J]. DISCRETE MATHEMATICS, 2002, 246 (1-3) : 29 - 55
  • [4] Banderier C, 2017, DISCRETE MATH THEOR, V19
  • [5] Nondecreasing Dyck paths and q-Fibonacci numbers
    Barcucci, E
    DelLungo, A
    Fezzi, S
    Pinzani, R
    [J]. DISCRETE MATHEMATICS, 1997, 170 (1-3) : 211 - 217
  • [6] Exhaustive generation of some lattice paths and their prefixes
    Barcucci, Elena
    Bernini, Antonio
    Pinzani, Renzo
    [J]. THEORETICAL COMPUTER SCIENCE, 2021, 878 : 47 - 52
  • [7] Equivalence classes of Dyck paths modulo some statistics
    Baril, Jean-Luc
    Petrossian, Armen
    [J]. DISCRETE MATHEMATICS, 2015, 338 (04) : 655 - 660
  • [8] On the generating functions of pattern-avoiding Motzkin paths
    Bean, Christian
    Bernini, Antonio
    Cervetti, Matteo
    Ferrari, Luca
    [J]. JOURNAL OF SYMBOLIC COMPUTATION, 2022, 113 : 126 - 138
  • [9] Bousquet-Mélou M, 2010, CONTEMP MATH, V520, P1
  • [10] Dyck path enumeration
    Deutsch, E
    [J]. DISCRETE MATHEMATICS, 1999, 204 (1-3) : 167 - 202