Robert Scherer: A criterion for asymptotic sharpness in the enumeration of simply generated trees
Abstract
Abstract: We study the identity y(x) = xA(y(x)), from the theory of rooted trees,
for appropriate generating functions y(x) and A(x) with non-negative integer
coefficients. A problem that has been studied extensively is to determine the
asymptotics of the coefficients of y(x) from analytic properties of the complex
function z → A(z), assumed to have a positive radius of convergence R. It is
well-known that the vanishing of A(x) − xA′(x) on (0, R) is sufficient to ensure
that y(r) < R, where r is the radius of convergence of y(x). This result has
been generalized in the literature to account for more general functional equations
than the one above, and used to determine asymptotics for the Taylor coefficients of
y(x). What has not been shown is whether that sufficient condition is also necessary.
We show here that it is, thus establishing a criterion for sharpness of the inequality
y(r) ≤ R. As an application, we prove a 1996 conjecture of Kuperberg regarding the
asymptotic growth rate of an integer sequence arising in the study of Lie algebra
representations.