Deepest Nodes in Marked Ordered Trees

Helmut Prodinger

doi:10.2478/amsil-2022-0015

.blurhash-client-img { display: none !important; }

Deepest Nodes in Marked Ordered Trees

Annales Mathematicae Silesianae

Volume 36 (2022): Issue 2 (September 2022)

By: Helmut Prodinger

Open Access

|Sep 2022

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 53 {5 \over 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.

References

[1] 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.10.1016/B978-1-4832-3187-7.50007-6
Open DOI Search in Google Scholar Back to article
[2] E. Deutsch, E. Munarini, and S. Rinaldi, Skew Dyck paths, J. Statist. Plann. Inference 140 2010, no. 8, 2191–2203.10.1016/j.jspi.2010.01.015
Open DOI Search in Google Scholar Back to article
[3] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 1980, no. 2, 125–161.10.1016/0012-365X(80)90050-3
Open DOI Search in Google Scholar Back to article
[4] P. Flajolet, X. Gourdon, and P. Dumas, Mellin transforms and asymptotics: harmonic sums, Theoret. Comput. Sci. 144 1995, no. 1–2, 3–58.10.1016/0304-3975(95)00002-E
Open DOI Search in Google Scholar Back to article
[5] P. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 1990, no. 2, 216–240.10.1137/0403019
Open DOI Search in Google Scholar Back to article
[6] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.10.1017/CBO9780511801655
Open DOI Search in Google Scholar Back to article
[7] R. Kemp, On the number of deepest nodes in ordered trees, Discrete Math. 81 1990, no. 3, 247–258.10.1016/0012-365X(90)90064-O
Open DOI Search in Google Scholar Back to article
[8] H. Prodinger, A walk in my lattice path garden, arXiv preprint. Avaliable at arXiv: 2111.14797.
Search in Google Scholar Back to article
[9] 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.10.1145/178365.178368
Open DOI Search in Google Scholar Back to article
[10] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, The OEIS Foundation Inc., http://oeis.org.
Search in Google Scholar Back to article
[11] V. Strehl, Two short proofs of Kemp’s identity for rooted plane trees, European J. Combin. 5 1984, no. 4, 373–376.10.1016/S0195-6698(84)80040-2
Open DOI Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.2478/amsil-2022-0015 | Journal eISSN: 2391-4238 (formerly 0860-2107) | Journal ISSN: 0860-2107

Journal RSS Feed

Language: English

Page range: 215 - 227

Submitted on: Feb 17, 2022

Accepted on: Aug 16, 2022

Published on: Sep 8, 2022

Published by: University of Silesia in Katowice, Institute of Mathematics

In partnership with: Paradigm Publishing Services

Keywords:

marked ordered trees,

MSC:

Related subjects:

© 2022 Helmut Prodinger, published by University of Silesia in Katowice, Institute of Mathematics
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Volume 36 (2022): Issue 2 (September 2022)