Deepest Nodes in Marked Ordered Trees

• Autorzy: Helmut Prodinger
• Języki publikacji: EN

Abstrakty

EN

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 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.(original abstract)

Słowa kluczowe

EN

Mathematics; Graphs; Functions

PL

Matematyka; Grafy; Funkcje

• Czasopismo: Annales Mathematicae Silesianae
• Rocznik: 2022
• Tom: 36 (2)
• Strony: 215--227

Twórcy

autor

Helmut Prodinger

• Stellenbosch University, South Africa

Bibliografia

• de Bruijn N.G., Knuth D.E., and Rice S.O., 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.
• Deutsch E., Munarini E., and Rinaldi S., Skew Dyck paths, J. Statist. Plann. Inference 140 (2010), no. 8, 2191-2203.
• Flajolet P., Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), no. 2, 125-161.
• Flajolet P., Gourdon X., and Dumas P., Mellin transforms and asymptotics: harmonic sums, Theoret. Comput. Sci. 144 (1995), no. 1-2, 3-58.
• Flajolet P. and Odlyzko A., Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990), no. 2, 216-240.
• Flajolet P. and Sedgewick R., Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.
• Kemp R., On the number of deepest nodes in ordered trees, Discrete Math. 81 (1990), no. 3, 247-258.
• Prodinger H., A walk in my lattice path garden, arXiv preprint. Avaliable at arXiv: 2111.14797.
• Salvy B. and Zimmermann P., 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.
• Sloane N.J.A., The On-Line Encyclopedia of Integer Sequences, The OEIS Foundation Inc., http://oeis.org.
• Strehl V., Two short proofs of Kemp's identity for rooted plane trees, European J. Combin. 5 (1984), no. 4, 373-376.

Identyfikatory

DOI

10.2478/amsil-2022-0015