Analytic Combinatorics – A Worked Example

This article gets things wrong and overcomplicates other things.

he confuses the characteristic equation for the generating function. This : T(z) = z + zT + zT^2 + zT^3 is the characteristic equation.

There is no simple generating function ,as it's not possible to easily invert a cubic closed in form.

Successive derivatives of the generating function are taken to find the coefficients of the infinite series that encodes the sought values. It's hard enough explaining this with a quadratic; a cubic so much more involved.

This so far beyond the scope of a blog post. You need to spend at least a few weeks working on this or take some college courses.

The article is correct. T(z) (in the warmup problem) is the generating function that counts the number of rooted ordered ternary trees, i.e. if we write T(z) = t_0 + t_1z + t_2z^2 + …, then t_n is the number of such trees with n nodes.

Yes there is no "simple" generating function, i.e. there's no simple expression for T(z). Nevertheless, T(z) (as further explained in another comment here in this thread) satisfies the equation T(z) = z + T(z) + zT(z)^2 + zT(z)^3, and this fact can be used to find the coefficients of T (i.e. the numbers t_n) via Lagrange inversion, and the code in the post does so and gets the same numbers as https://oeis.org/A036765.

(You use the term "characteristic equation", but that is a term only used in the context of linear recurrence relations AFAIK, and not applicable here.)

(Also IMO the post does not overcomplicate anything; what it presents is in fact the easiest way of solving the problem — that of finding the asymptotics of the number of unordered rooted ternary trees, up to isomorphism. If you think you have a simpler method even for counting small cases, feel free to post an answer at https://math.stackexchange.com/questions/5050941/counting-tr....)

thanks for clearing it up