Deepest Nodes in Marked Ordered Trees

Prodinger, Helmut

doi:10.2478/amsil-2022-0015

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 $\frac{5}{3}$ {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
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
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
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
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
Search in Google Scholar Back to article
[6] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.10.1017/CBO9780511801655
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
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
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
Search in Google Scholar Back to article

Deepest Nodes in Marked Ordered Trees

Abstract

Paradigm

My account