Logo image
Back
Limit distribution for the maximum degree of a random recursive tree
Journal article   Open access   Peer reviewed

Limit distribution for the maximum degree of a random recursive tree

William Goh and Eric Schmutz
Journal of computational and applied mathematics, v 142(1), pp 61-82
2002
DOI: https://doi.org/10.1016/S0377-0427(01)00460-5
url
https://doi.org/10.1016/s0377-0427(01)00460-5View
Published, Version of Record (VoR)Open Access (Publisher-Specific),  Open

Abstract

Asymptotic enumeration Degree Exponential series Recursive Szegő Tree
If a recursive tree is selected uniformly at random from among all recursive trees on n vertices, then the distribution of the maximum in-degree Δ is given asymptotically by the following theorem: for any fixed integer d, P n(Δ⩽⌊μ n⌋+d)= exp(−2{ μ n}−d−1 )+ o(1) as n→∞, where μ n= log 2 n . (As usual, ⌊ μ n ⌋ denotes the greatest integer less than or equal to μ n , and { μ n }= μ n −⌊ μ n ⌋.) The proof makes extensive use of asymptotic approximations for the partial sums of the exponential series.

Metrics

15 Record Views
15 citations in Web of Science
16 citations in Scopus

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Web of Science research areas
Mathematics, Applied
Logo image