×

On the limiting distributions of the total height on families of trees. (English) Zbl 1416.05021

Summary: A symbolic-computational algorithm, fully implemented in Maple, is described, that computes explicit expressions for generating functions that enable the efficient computations of the expectation, variance, and higher moments, of the random variable ‘sum of distances to the root’, defined on any given family of rooted ordered trees (defined by degree restrictions). Taking limits, we confirm, via elementary methods, the fact, due to D. Aldous [Ann. Probab. 21, No. 1, 248–289 (1993; Zbl 0791.60009)], and expanded by S. Janson [Probab. Surv. 9, 103–252 (2012; Zbl 1244.60013)] and others, that the limiting (scaled) distributions are all the same, and coincide with the limiting distribution of the same random variable, when it is defined on labeled rooted trees.

MSC:

05A15 Exact enumeration problems, generating functions
05C05 Trees
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] David Aldous, The continuum random tree II: an overview, Stochastic analysis 167 (1991), 23-70. · Zbl 0791.60008
[2] David Aldous, The continuum random tree III, Ann. Probab. 21 (1993), 248-289. · Zbl 0791.60009
[3] Shalosh B. Ekhad and Doron Zeilberger, Explicit expressions for the variance and higher moments of the size of a simultaneous core partition and its limiting distribution, The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, http://www.math.rutgers.edu/ zeilberg/mamarim/mamarimhtml/stcore.html. · Zbl 1391.11050
[4] Shalosh B. Ekhad and Doron Zeilberger, Going back to Neil Sloane’s FIRST LOVE (OEIS Sequence A435): on the total heights in rooted labeled trees, The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, http://www.math.rutgers.edu/ zeilberg/mamarim/mamarimhtml/a435.html. · Zbl 1301.92073
[5] Shalosh B. Ekhad and Doron Zeilberger, Automatic proofs of asymptotic ABNORMALITY (and much more!) of natural statistics defined on Catalan-counted combinatorial families, The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, http://www.math.rutgers.edu/ zeilberg/mamarim/mamarimhtml/abnormal.html. · Zbl 1302.05032
[6] Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009. (Free download from Flajolet’s homepage.) · Zbl 1165.05001
[7] Svante Janson, Brownian excursion area, Wright’s constants in graph enumeration, and other Brownian areas, Probability Surveys 3 (2007), 80-145. Available on line from https://arxiv.org/abs/ 0704.2289 · Zbl 1189.60147
[8] Svante Janson, Patterns in random permutations avoiding the pattern 132, Available on line from https://arxiv.org/abs/1401.5679 · Zbl 1381.60028
[9] Svante Janson, Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation, Probability Surveys 9 (2012), 103-252. Available on line from http://www2.math.uu.se/ svante/papers/sj264.pdf · Zbl 1296.60234
[10] Svante Janson, The Wiener index of simply generated trees, Random Structures and algorithms 22(4) (2003), 337-358. Available on line from http://www2.math.uu.se/ svante/papers/sj146.pdf · Zbl 1025.05021
[11] Jean-Fran¸cois Marckert and Abdelkader Mokkadem, The depth first processes of Galton– Watson trees converge to the same Brownian excursion, Ann. of Probab. 31(3) (2003), 16551678. Available on line from http://projecteuclid.org/euclid.aop/1055425793. · Zbl 1049.05026
[12] John Riordan and Neil J. A. Sloane, The enumeration of rooted trees by total height, J. Australian Math. Soc. 10(1969), 278-282. Available on line from: http://neilsloane.com/doc/riordan-enum-trees-by-height.pdf. · Zbl 0183.28404
[13] Dan Romik, The Surprising Mathematics of Longest Increasing Subsequences, Cambridge University Press, 2015. · Zbl 1345.05003
[14] L. Tak‘acs, On the total heights of random rooted trees, J. Appl. Probab., 29(3) (1992), 543-556. · Zbl 0768.05030
[15] L. Tak‘acs, Limit theorems for random trees, Proc. Natl. Acad. Sci. USA, 89 (1992), 50115014.
[16] L. Tak‘acs, The asymptotic distribution of the total heights of random rooted trees, Acta Sci. Math. (Szeged) 57(1-4) (1993), 613-625.
[17] S. Wagner, On the Wiener index of random trees, Discrete Math. 312(9) (2012), 1502-1511. · Zbl 1239.05057
[18] Doron Zeilberger, Doron Gepner’s statistics on words in {1, 2, 3}* is (most probably) asymptotically logistic, The Personal Journal of Shalosh B.
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.