Limit distribution for the maximum degree of a random recursive tree

摘要

If a recursive tree is selected uniformly at random from among all recursive trees on v 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.