Psi‐series method for equality of random trees and quadratic convolution recurrences1. Issue 1 (11th May 2012) - Chern, Hua‐Huai; Fernández‐Camacho, María‐Inés; Hwang, Hsien‐Kuei; Martínez, Conrado
Abstract An unusual and surprising expansion of the form <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3z37jp8h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />pn=ρ−n−1(6n+185+3363125n−5+10083125n−6+smaller order terms), </alternatives> as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3z37jp7z" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n→∞</alternatives>, 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 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 © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 67–108, 2014