Limit distributions for coefficients of iterates of polynomials with applications to combinatorial enumerations

This paper studies coefficients yh, _n of sequences of polynomials [formula omitted] defined by non-linear recurrences. A typical example to which the results of this paper apply is that of the sequence B₀(x) = 1, B_h+1(x) = 1 +xB_h(x)² for h ≥ 0, which arises in the study of binary trees. For a wide class of similar sequences a general distribution law for the coefficients y_{hin as}functions of n with h fixed is established. It follows from this law that in many interesting cases the distribution is asymptotically Gaussian near the peak. The proof relies on the saddle point method applied in a region where the polynomials grow doubly exponentially as h —>. ∞. Applications of these results include enumerations of binary trees and 2–3 trees. Other structures of interest in computer science and combinatorics can also be studied by this method or its extensions.