Lagrange inversion and tree enumeration

Let $\Phi(u)$ be a formal power series over the rationals with nonzero constant term. There is a unique series $T(x)$ with zero constant term satisfying $T=x\Phi(T)$. The coefficient at degree n on the right uses coefficients of T only through degree n minus one, so it determines the next coefficient recursively. Zero constant term makes composition meaningful coefficientwise. No assumption that the series converges numerically near zero is needed for this formal existence and uniqueness statement.

Lagrange inversion gives a direct coefficient formula for powers of that solution. We state the version with positive integers n and k satisfying n at least k, and characteristic-zero coefficients so division by n is available. The formula is a theorem of formal power-series algebra, not a claim that repeated numerical substitution converges. Analytic inversion is a related theory with additional domain and regularity hypotheses. Here it is the finite coefficient calculation that extracts exact counts.

A rooted plane tree has a root and an ordered list of children at every vertex. Size counts all vertices. Removing the root leaves a sequence of smaller rooted plane trees, including the empty sequence when the root is a leaf. The root contributes one factor of the size marker, while the sequence contributes a geometric formal series. This yields the implicit equation with child series one divided by one minus T. The ordering distinguishes two children of different shapes when swapped.

Taking the first-power case of Lagrange inversion gives a binomial coefficient divided by the vertex count. It agrees with the shifted Catalan formula: a tree with n vertices has n minus one edges. The division is justified by the inversion theorem; a combinatorial proof can also use cyclic rotations of degree sequences with an admissible-prefix condition. Simply dividing all degree sequences by n without that argument would be unsafe, since symmetry quotients in general need not have constant fiber sizes.

If each vertex has three distinguished child slots, each empty or occupied by a subtree, the local factor is $(1+T)^3$. This counts a different plane family from an arbitrary ordered list. Lagrange inversion then extracts the coefficient of degree n minus one in $(1+u)^{3n}$. Slots remain distinguished even when some are empty, so a sole left child differs from a sole middle child. An ordinary unlabeled rooted tree with unordered children has neither of these simple local descriptions.

For rooted trees on distinct labels with unordered children, use an EGF instead. The children are a set of nonempty labeled rooted trees, yielding $R=xe^R$. Inversion gives the normalized coefficient $n^{n-1}/n!$; multiplying by n factorial recovers the number of rooted labeled trees. This example highlights why identical-looking formal coefficient operations can encode different counts. The equation must come from a justified class construction, and the final coefficient must be interpreted in its original OGF or EGF convention.