Name
Title | ||
|---|---|---|
Psi-series method for equality of random trees and quadratic convolution recurrences. |
Abstract | ||
|---|---|---|
An unusual and surprising expansion of the form p(n)=-rho(-n-1) (6n + 18/5 + 336/3125n(-5) + 1008/3125 n(-6) + smaller order terms), as n ->infinity, is derived for the probability p(n) that two randomly chosen binary search trees are identical (in shape, hence in labels of all corresponding nodes). A quantity arising in the analysis of phylogenetic trees is also proved to have a similar asymptotic expansion. Our method of proof is new in the literature of discrete probability and the analysis of algorithms, and it is based on the logarithmic psi-series expansions for nonlinear differential equations. Such an approach is very general and applicable to many other problems involving nonlinear differential equations; many examples are discussed in this article and several attractive phenomena are discovered.Copyright (c) 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 67-108, 2014 |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1002/rsa.20428 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | Field | DocType |
psi-series method,nonlinear differential equations,random trees,recursive structures,singularity analysis,asymptotic analysis | Discrete mathematics,Combinatorics,Of the form,Convolution,Analysis of algorithms,Quadratic equation,Asymptotic expansion,Logarithm,Asymptotic analysis,Binary search tree,Mathematics | Journal |
Volume | Issue | ISSN |
44.0 | 1.0 | 1042-9832 |
Citations | PageRank | References |
2 | 0.39 | 15 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hua-Huai Chern | 1 | 78 | 7.25 |
| María-Inés Fernández-Camacho | 2 | 2 | 0.39 |
| Hsien-Kuei Hwang | 3 | 365 | 38.02 |
| Conrado Martínez | 4 | 232 | 22.17 |