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

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.