Left to right maxima in Dyck prefixes
DOI:
https://doi.org/10.13069/jacodesmath.v11i1.248Keywords:
Dyck prefixes, Generating functions, AsymptoticAbstract
In a Dyck path, a peak which is strictly (weakly) higher than all the preceding peaks is called a strict (weak) left-to-right maximum. By dropping the restrictions for the path to end on the $x$-axis, one obtains Dyck prefixes. We obtain explicit generating functions for both weak and strict left-to-right maxima in Dyck prefixes. The proofs of the associated asymptotics make use of analytic techniques such as Mellin transforms, singularity analysis and formal residue calculus.
Received: 26 April 2022 | Accepted: 28 June 2023Downloads
References
A. Bacher, A. Bernini, L. Ferrari, B. Gunby, R. Pinzani, and J. West, The Dyck pattern poset, Discrete Math. 321 (2014) 12–23.
A. Blecher, C. Brennan, and A. Knopfmacher, Water capacity of Dyck paths, Adv. in Appl. Math. 112 (2020) 101945.
A. Blecher and A. Knopfmacher, Left to right maxima in Dyck paths, arXiv preprint arXiv:2107.03102 (2021).
E. Czabarka, R. Flórez, and L. Junes, Some enumerations on non-decreasing Dyck paths, Electron. J. Combin. 22(1) (2015) #P1.3.
E. Czabarka, R. Flórez, L. Junes, and J. Ramírez, Enumerations of peaks and valleys on non-decreasing Dyck paths, Discrete Math. 341(10) (2018) 2789–2807.
E. Deutsch, A bijection on Dyck paths and its consequences, Discrete Math. 179(1-3) (1998) 253–256.
E. Deutsch, Dyck path enumeration, Discrete Math. 204(1-3) (1999) 167–202.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.
R. Kemp, On the average depth of a prefix of the Dycklanguage $D_1$, Discrete Math. 36(2) (1981) 155–170.
A. Knopfmacher and T. Mansour, Record statistics in a random composition, Discrete Appl. Math. 160(4-5) (2012) 593–603.
A. Knopfmacher, T. Mansour, and S. Wagner, Records in set partitions, Electron. J. Combin. 17(1) (2010) #R109.
K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, Nonleft peaks in Dyck paths: a combinatorial approach, Discrete Math. 337 (2014) 97–105.
W. Panny and H. Prodinger, The expected height of paths for several notions of height, Studia Sci. Math. Hungar. 20(1-4) (1985) 119–132.
H. Prodinger, A note on a result of R. Kemp on R-typly rooted planted plane trees, Computing 28(4) (1982) 363–366.
H. Prodinger, The height of planted plane trees revisited, Ars Combin. 16(B) (1983) 51–55.
H. Prodinger, Some analytic techniques for the investigation of the asymptotic behaviour of tree parameters, Bull. EATCS 47 (1992) 180–199.
H. Prodinger, The location of the first maximum in the first sojourn of a Dyck path, Discrete Math. Theor. Comput. Sci. 10(3) (2008) 125–134.
A. Sapounakis, I. Tasoulas, and P. Tsikouras, Enumeration of strings in Dyck paths: a bijective approach, Discrete Math. 309(10) (2009) 3032–3039.
