Abstract :
Let ℓn be the number of leftist trees with n nodes. The corresponding (ordinary) generating function ℓ(x) is shown to satisfy an explicit functional equation, from which a specific recurrence for the ℓn is obtained. Some basic analytic properties of ℓ(x) are uncovered. Then the problem of determining average quantities (expected additive weights, in the notation of Kemp (Acta Inform. 26 (1989) 711–740)) related to the distribution of nodes is re-analysed. Finally, the average height of leftist trees is shown to be asymptotic to n1/2, apart from a multiplicative constant that can be evaluated with high accuracy.
