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]  
[Anonymous], 2014, PLOS ONE, DOI DOI 10.1371/journal.pone.0096223
[2]  
Asinowski A., 2020, Semin. Lothar. Comb, V84
[3]   Basic analytic combinatorics of directed lattice paths [J].
Banderier, C ;
Flajolet, P .
THEORETICAL COMPUTER SCIENCE, 2002, 281 (1-2) :37-80
[4]   Generating functions for generating trees [J].
Banderier, C ;
Bousquet-Mélou, M ;
Denise, A ;
Flajolet, P ;
Gardy, D ;
Gouyou-Beauchamps, D .
DISCRETE MATHEMATICS, 2002, 246 (1-3) :29-55
[5]  
Banderier C, 2017, DISCRETE MATH THEOR, V19
[6]   Nondecreasing Dyck paths and q-Fibonacci numbers [J].
Barcucci, E ;
DelLungo, A ;
Fezzi, S ;
Pinzani, R .
DISCRETE MATHEMATICS, 1997, 170 (1-3) :211-217
[7]   Exhaustive generation of some lattice paths and their prefixes [J].
Barcucci, Elena ;
Bernini, Antonio ;
Pinzani, Renzo .
THEORETICAL COMPUTER SCIENCE, 2021, 878 :47-52
[8]   Equivalence classes of Dyck paths modulo some statistics [J].
Baril, Jean-Luc ;
Petrossian, Armen .
DISCRETE MATHEMATICS, 2015, 338 (04) :655-660
[9]   On the generating functions of pattern-avoiding Motzkin paths [J].
Bean, Christian ;
Bernini, Antonio ;
Cervetti, Matteo ;
Ferrari, Luca .
JOURNAL OF SYMBOLIC COMPUTATION, 2022, 113 :126-138
[10]  
Bousquet-Mélou M, 2010, CONTEMP MATH, V520, P1