Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-27T22:20:32.560Z Has data issue: false hasContentIssue false
  • English
  • Français

On the total heights of random rooted trees

Part of: Graph theory

Published online by Cambridge University Press:  14 July 2016

Lajos Takacs
Lajos Takacs*
Affiliation:
Case Western Reserve University
*
∗Postal address: 2410 Newbury Drive, Cleveland Heights, OH 44118, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Denote by Sn the set of all distinct rooted trees with n labeled vertices. Define τn as the total height of a tree chosen at random in the set Sn, assuming that all the possible nn–1 choices are equally probable. The total height of a tree is defined as the sum of the heights of its vertices. The height of a vertex in a rooted tree is the distance from the vertex to the root of the tree, that is, the number of edges in the path from the vertex to the root. This paper is concerned with the distribution and the moments of τn and their asymptotic behavior as n → ∞.

Keywords

RANDOM TREESTOTAL HEIGHTLIMIT DISTRIBUTION

MSC classification

Primary: 05C05: Trees
Type
Research Papers
Information
Journal of Applied Probability , Volume 29 , Issue 3 , September 1992 , pp. 543 - 556
Copyright
Copyright © Applied Probability Trust 1992 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Abramowitz, M. and Stegun, I. A. (1965) Handbook of Mathematical Functions. Dover, New York.Google Scholar
[2] Carleman, T. (1922) Sur le problème des moments. C. R. Acad. Sci. Paris 174, 1680–1682.Google Scholar
[3] Cayley, A. (1889) A theorem on trees. Quart. J. Pure Appl. Math. 23. 376–378. (In The Collected Mathematical Papers of Arthur Cayley, Vol. XIII, pp. 26-28, Cambridge University Press, 1897.) Google Scholar
[4] Darling, D. A. (1983) On the supremum of a certain Gaussian process. Ann. Prob. 11, 803–806.Google Scholar
[5] Fréchet, M. and Shohat, J. (1931) A proof of the generalized second-limit theorem in the theory of probability. Trans. Amer. Math. Soc. 33, 533–543.Google Scholar
[6] Miller, J. C. P. (1946) The Airy Integral. Cambridge University Press.Google Scholar
[7] Riordan, J. and Sloane, N. J. A. (1969) The enumeration of rooted trees by total height. J. Austral. Math. Soc. 10, 278–282.Google Scholar
[8] Slater, L. J. (1960) Confluent Hypergeometric Functions. Cambridge University Press.Google Scholar
[9] Takács, L. (1990) On Cayley's formula for counting forests. J. Combinatorial Theory A53, 321–323.Google Scholar
[10] Takács, L. (1991) A Bernoulli excursion and its various applications. Adv. Appl. Prob. 23, 557–585.Google Scholar
[11] Wolfram, S. (1988) Mathematica. A System for Doing Mathematics by Computer. Addison-Wesley, Redwood City, CA.Google Scholar