Deepest nodes in marked ordered trees
Abstract
A variation of ordered trees, where each rightmost edge might be marked or not, if it does not lead to an endnode, is investigated. These marked ordered trees were introduced by E. Deutsch et al. to model skew Dyck paths. We study the number of deepest nodes in such trees. Explicit generating functions are established and the average number of deepest nodes, which approaches 5/3 when the number of nodes gets large. This is to be compared to standard ordered trees where the average number of deepest nodes approaches 2.
Keywords
marked ordered trees; skew Dyck paths; generating functions
References
N.G. de Bruijn, D.E. Knuth, and S.O. Rice, The average height of planted plane trees, in: R.C. Read (ed.), Graph Theory and Computing, Academic Press, New York-London, 1972, pp. 15–22.
E. Deutsch, E. Munarini, and S. Rinaldi, Skew Dyck paths, J. Statist. Plann. Inference 140 (2010), no. 8, 2191–2203.
P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), no. 2, 125–161.
P. Flajolet, X. Gourdon, and P. Dumas, Mellin transforms and asymptotics: harmonic sums, Theoret. Comput. Sci. 144 (1995), no. 1–2, 3–58.
P. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990), no. 2, 216–240.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.
R. Kemp, On the number of deepest nodes in ordered trees, Discrete Math. 81 (1990), no. 3, 247–258.
H. Prodinger, A walk in my lattice path garden, arXiv preprint. Avaliable at arXiv: 2111.14797.
B. Salvy and P. Zimmermann, GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM Trans. Math. Software 20 (1994), no. 2, 163–177.
N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, The OEIS Foundation Inc., http://oeis.org.
V. Strehl, Two short proofs of Kemp’s identity for rooted plane trees, European J. Combin. 5 (1984), no. 4, 373–376.
Department of Mathematical Sciences, Stellenbosch University & NITheCS (National Institute for Theoretical and Computational Sciences), South Africa South Africa
https://orcid.org/0000-0002-0009-8015
This work is licensed under a Creative Commons Attribution 4.0 International License.
The Copyright Holders of the submitted text are the Author and the Journal. The Reader is granted the right to use the pdf documents under the provisions of the Creative Commons 4.0 International License: Attribution (CC BY). The user can copy and redistribute the material in any medium or format and remix, transform, and build upon the material for any purpose.
- License
This journal provides immediate open access to its content under the Creative Commons BY 4.0 license (http://creativecommons.org/licenses/by/4.0/). Authors who publish with this journal retain all copyrights and agree to the terms of the above-mentioned CC BY 4.0 license. - Author’s Warranties
The author warrants that the article is original, written by stated author/s, has not been published before, contains no unlawful statements, does not infringe the rights of others, is subject to copyright that is vested exclusively in the author and free of any third party rights, and that any necessary written permissions to quote from other sources have been obtained by the author/s. - User Rights
Under the Creative Commons Attribution license, the users are free to share (copy, distribute and transmit the contribution) and adapt (remix, transform, and build upon the material) the article for any purpose, provided they attribute the contribution in the manner specified by the author or licensor. - Co-Authorship
If the article was prepared jointly with other authors, the signatory of this form warrants that he/she has been authorized by all co-authors to sign this agreement on their behalf, and agrees to inform his/her co-authors of the terms of this agreement.
