Lagrange inversion theorem

Remarks

Proof idea: work with formal Laurent series, where the coefficient of $w^{-1}$ in a derivative is always $0$. Change the variable from $z$ to $w = T(z)$, so $z = w / \phi(w)$. The coefficient of $z^{-1}$ in $z^{-n-1} H(T(z))$ becomes a coefficient of $w^{-1}$, and an integration by parts gives the formula.

Example: rooted labelled trees have the exponential generating function $T(z) = z e^{T(z)}$. With $\phi(w) = e^w$, the theorem gives $[z^n] T = \frac{1}{n} \cdot \frac{n^{n-1}}{(n-1)!} = \frac{n^{n-1}}{n!}$. So there are $n^{n-1}$ rooted trees on $n$ labelled vertices.

Example: with $\phi(w) = (1 + w)^2$, the series $T$ counts binary trees by internal nodes. The theorem gives $[z^n] T = \frac{1}{n} \binom{2n}{n-1}$, which is the Catalan number $C_n$.

The hypothesis $\phi(0) \ne 0$ makes the problem meaningful. If $\phi(0) = 0$, then $T = 0$ is the only solution with $T(0) = 0$, and the equation counts nothing. Characteristic $0$ is used to divide by $n$. There is also an analytic version for holomorphic $\phi$ near $0$, which then gives the Taylor series of the inverse function.

Going deeper

For a student

The theorem is the main tool for counting trees and tree-like structures. A family of rooted trees defined by the allowed numbers of children has a generating function with $T = z\, \phi(T)$, where $\phi$ records the allowed numbers of children. In the symbolic method such equations arise at once from the recursive description of the trees. The form with $H$ counts forests, since a sequence of $k$ trees has generating function $T^k$. Equivalently, the theorem computes the coefficients of the compositional inverse of $z / \phi(z)$.