Lagrange Inversion Theorem

The Lagrange inversion theorem is a fundamental tool for extracting coefficients from implicitly defined generating functions. It provides explicit formulas for counting recursive combinatorial structures such as trees, which are naturally described by functional equations.

TheoremLagrange Inversion Theorem

Let $\phi(t)$ be a formal power series with $\phi(0) \neq 0$ , and let $y$ be defined implicitly by: $y = x\phi(y)$

Then for any formal power series $H(t)$ and any positive integer $n$ : $[x^n]H(y) = \frac{1}{n}[t^{n-1}](H'(t)\phi(t)^n)$

In particular, taking $H(t) = t$ : $[x^n]y = \frac{1}{n}[t^{n-1}]\phi(t)^n$

ExampleCatalan Numbers via Lagrange Inversion

The Catalan generating function $C(x)$ satisfies: $C(x) = 1 + xC(x)^2$

Rewrite as $C(x) = x(1 + C(x)^2)/x$ . Let $y = C(x)$ and $\phi(y) = (1 + y^2)/x$ ... Actually, better to use the form: $C(x) - 1 = xC(x)^2$

Let $T(x) = xC(x)$ , so $C(x) = 1 + T(x)$ and: $T(x) = x(1 + T(x))^2$

This is in the form $T = x\phi(T)$ with $\phi(t) = (1+t)^2$ . By Lagrange inversion: $[x^n]T(x) = \frac{1}{n}[t^{n-1}](1+t)^{2n} = \frac{1}{n}\binom{2n}{n-1} = \frac{1}{n}\cdot\frac{(2n)!}{(n-1)!(n+1)!} = \frac{1}{n+1}\binom{2n}{n}$

Thus $C_n = [x^n]C(x) = [x^{n-1}]T(x) = \frac{1}{n}\binom{2n-2}{n-1} = C_{n-1}$ for $n \geq 1$ .

Actually, directly: $C(x) = 1 + xC(x)^2$ gives $[x^n]C(x) = [x^{n-1}]C(x)^2 = \sum_{k=0}^{n-1} C_k C_{n-1-k}$ for $n \geq 1$ , with $C_0 = 1$ , yielding the Catalan recurrence.

Proof

The proof uses complex analysis (residue calculus) or purely algebraic methods. We sketch the algebraic approach:

Let $y = \sum_{n=1}^\infty y_n x^n$ satisfy $y = x\phi(y)$ . Then: $\sum_{n=1}^\infty y_n x^n = x\phi\left(\sum_{n=1}^\infty y_n x^n\right)$

Comparing coefficients of $x^n$ : $y_n = [t^{n-1}]\phi(t)^n \cdot \frac{1}{n}$

through a careful inductive argument. The key is that $[x^n]y$ depends only on $\phi$ and not on the specific solution $y$ .

For the general case with $H(y)$ , we use the chain rule: $\frac{d}{dx}H(y) = H'(y)\frac{dy}{dx}$

Since $y = x\phi(y)$ , differentiation gives: $\frac{dy}{dx} = \phi(y) + x\phi'(y)\frac{dy}{dx}$

Solving: $\frac{dy}{dx} = \frac{\phi(y)}{1 - x\phi'(y)}$ .

The coefficient $[x^{n-1}]\frac{d}{dx}H(y) = n[x^n]H(y)$ can be computed using the implicit function and power series manipulation.

■

ExampleBinary Trees

A binary tree is either empty or consists of a root with two subtrees. If $B(x)$ counts binary trees: $B(x) = 1 + xB(x)^2$

This is identical to the Catalan equation. The number of binary trees with $n$ internal nodes is $C_n$ .

For plane trees (rooted ordered trees), if $T(x)$ is the generating function: $T(x) = x(1 + T(x) + T(x)^2 + T(x)^3 + \cdots) = \frac{x}{1 - T(x)}$

So $T(x) = x/(1-T(x))$ , giving $T = x + xT$ or $T = x/(1-x)$ ... This doesn't work. Actually: $T(x) = x(1 + T(x))$ is for sequences, giving $T = x + xT$ , so $T = x/(1-x)$ , not interesting.

The correct equation for plane trees is: $T(x) = x \cdot e^{T(x)}$

Using Lagrange inversion with $\phi(t) = e^t$ : $[x^n]T(x) = \frac{1}{n}[t^{n-1}]e^{nt} = \frac{n^{n-1}}{n!} \cdot (n-1)! = \frac{n^{n-1}}{n}$

Wait, $[t^{n-1}]e^{nt} = \frac{n^{n-1}}{(n-1)!}$ , so: $[x^n]T(x) = \frac{1}{n} \cdot \frac{n^{n-1}}{(n-1)!}$

The number of labeled rooted trees on $n$ vertices is $n^{n-1}$ (Cayley's formula), but the generating function gives $\frac{n^{n-1}}{n!}$ per $x^n$ ... This is the EGF.

TheoremExtended Lagrange Inversion

If $f(x) = xg(f(x))$ and $h(x)$ is any power series, then: $[x^n]h(f(x)) = \frac{1}{n}[z^{n-1}]h'(z)g(z)^n + [x^0]h(x) \cdot \delta_{n,0}$

This generalizes to extracting any function composition involving the implicit function.

Remark

The Lagrange inversion theorem is fundamental in:

Tree enumeration: Counting various classes of trees (binary, plane, labeled, unlabeled)
Species theory: Analyzing combinatorial species and their generating functions
Asymptotic analysis: Deriving growth rates of sequences via singularity analysis
Parking functions: Counting parking arrangements and related permutation statistics

The theorem bridges recursive definitions and explicit formulas, making it indispensable for advanced enumeration.

Lagrange inversion exemplifies the power of generating functions to transform complex recursive structures into tractable algebraic problems.