A note on subtrees rooted along the primary path of a binary tree

Abstract

Let F n denote the set of rooted binary plane trees with n external nodes, for given T ∈ F n let u i ( T ) be the altitude i node along the primary path of T , and let δ i ( T ) denote the number of external nodes in the induced subtree rooted at u i ( T ). We set δ i ( T ) = 0 if i is greater than the length of the primary path of T . We prove lim n →∞ ∑ i ≤ x / n E n { δ i }/∑ i <∞ E n { δ i } = G ( x ), where E n denotes the average over trees T ∈ F n and where the distribution function G is determined by its moments, for which we present an explicit expression.