Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Psi-series method for equality of random trees and quadratic convolution recurrences

Autor
Chern, H.; Fernández Camacho, María Inés; Hwang, H.; Martinez, C.
Tipus d'activitat
Article en revista
Revista
Random structures and algorithms
Data de publicació
2014-01
Volum
44
Número
1
Pàgina inicial
67
Pàgina final
108
DOI
https://doi.org/10.1002/rsa.20428 Obrir en finestra nova
URL
http://onlinelibrary.wiley.com/doi/10.1002/rsa.20428/abstract Obrir en finestra nova
Resum
An unusual and surprising expansion of the form pn=¿-n-1(6n+185+3363125n-5+10083125n-6+smaller order terms), as n¿8, is derived for the probability pn 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 ...
Paraules clau
Asymptotic analysis, Nonlinear differential equations, Psi-series method, Random trees, Recursive structures, Singularity analysis
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

  • Chern, Hua-huai  (autor)
  • Fernández Camacho, María Inés  (autor)
  • Hwang, Hsien-Kuei  (autor)
  • Martinez Parra, Conrado  (autor)