Analytic Combinatorics – A Worked Example

I find this interesting but the nomenclature escapes me: How is T(z) = z + zT + zT^2 + ... ? I find the jump from the functional programming description of the tree to this recurrence relation not intuitive

Generating functions are definitely strange and unintuitive, but they can be really helpful for combinatorics.

The introduction to generating functions in this well known text on the subject (at the beginning of Chapter 1) might be more helpful than the Wikipedia article linked in the original post:

https://www2.math.upenn.edu/~wilf/gfology2.pdf

From that text:

> Although giving a simple formula for the members of the sequence may be out of the question, we might be able to give a simple formula for the sum of a power series, whose coefficients are the sequence that we’re looking for.

I'm afraid the author is writing for an audience that's familiar with generating functions. It's using a common trick in analytic combinatorics, the notation is actually "shorthand".

Very informally, let T(z) be the generating function where the coefficient of the z^n term is the number of trees we are searching with exactly n nodes.

We know from the functional description that such a tree can be:

  - a leaf;
  - a node with 1 child;
  - a node with 2 children;
  - a node with 3 children.

A leaf is a tree with one node and that's it, so it "contributes" as a single tree of size 1.

How many trees of size n are there that fall in the second case? Exactly as many as the total trees of size (n-1), hence this case "contributes" as zT(z).

How many trees of size n fall in the third case? That's a bit harder to see, because now you have (n-1) nodes in total, split between the two branches. So you can have 1 in the left branch and n-2 in the right branch, 2 left n-3 right and so on. With a bit of basic combinatorics you can notice that this is exactly the convolution product of the series with itself, in analytical terms T^2(z). Hence the third case "contributes" for zT^2(z).

The fourth case is similar.

At this point we have constructed the inverse of the generating function we are looking for, i.e. z as a function of T(z) rather than the reverse, but luckily there's a standard trick for this: Lagrange inversion.

I had the same question as OP, passing knowledge of generating functions was not enough to see the link between the description and formula.

Your explanation was exactly what I needed, thanks.

He doesn't explain any of the notation, like how the brackets [z] work. Also the generating function he supplies is is wrong.