×

Moments of level numbers of leaves in binary trees. (English) Zbl 0989.05022

The paper derives closed formulae for all moments for the random variable “height of leaf \(j\) in the binary tree of size \(n\).” Case of \(t\)-ary trees is studied as well. The results are achieved in spite of earlier pessimism on the possibility of such closed formulae.

MSC:

05C05 Trees
05A15 Exact enumeration problems, generating functions
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Drmota, M., The height distribution of leaves in rooted trees, Discrete Mathematics and Applications, 4, 45-58 (1994) · Zbl 0801.60074
[2] Fisz, M., Probability Theory and Mathematical Statistics. (1963), Wiley: Wiley New York · Zbl 0123.34504
[3] Gittenberger, B., 1995. Die Konvergenz spezieller stochastischer Prozesse gegen die Brownsche Exkursion und deren lokale Zeit. PhD thesis, Technische Universität Wien, 1995.; Gittenberger, B., 1995. Die Konvergenz spezieller stochastischer Prozesse gegen die Brownsche Exkursion und deren lokale Zeit. PhD thesis, Technische Universität Wien, 1995.
[4] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0836.00001
[5] Gutjahr, W., The variance of level numbers in certain families of trees, Random Struct. Algorithms, 3, 361-374 (1992) · Zbl 0772.05036
[6] Gutjahr, W.; Pflug, G., The asymptotic distribution of leaf heights in binary trees., Graphs Combin., 8, 243-251 (1992) · Zbl 0772.05034
[7] Kirschenhofer, P., On the height of leaves in binary trees, J. Combin. Inform. System Sci., 8, 44-60 (1983) · Zbl 0629.05031
[8] Kirschenhofer, P., Some new results on the average height of binary trees, Ars Combin., 16A, 255-260 (1983) · Zbl 0534.05028
[9] Kirschenhofer, P., Asymptotische Untersuchungen zur durchschnittlichen Gestalt gewisser Graphenklassen., (Hlawka, E., Zahlentheoretische Analysis, Vol. 1114. Zahlentheoretische Analysis, Vol. 1114, Lecture Notes in Mathematics (1985), Springer: Springer Berlin), 40-54 · Zbl 0566.05021
[10] Panholzer, A.; Prodinger, H., Descendants and ascendants in binary trees, Discrete Math. Theoret. Comput. Sci., 1, 247-266 (1997) · Zbl 0930.05030
[11] Petkovšek, M., Wilf, H., Zeilberger, D., \(1996. AB\); Petkovšek, M., Wilf, H., Zeilberger, D., \(1996. AB\)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.