Enumerations of trees and forests related to branching processes and random walks
In a Galton-Watson branching process with offspring distribution $(p_0, p_1, \ldots )$ started with $k$ individuals, the distribution of the total progeny is identical to the distribution of the first passage time to $-k$ for a random walk started at 0 which takes steps of size $j$ with probability $p_{j+1}$ for $j \ge -1$. The formula for this distribution is a probabilistic expression of the Lagrange inversion formula for the coefficients in the power series expansion of $f(z)^k$ in terms of those of $g(z)$ for $f(z)$ defined implicitly by $f(z) = z g(f(z))$. The Lagrange inversion formula is the analytic counterpart of various enumerations of trees and forests which generalize Cayley's formula $k n^{n-k-1}$ for the number of rooted forests labeled by a set of size $n$ whose set of roots is a particular subset of size $k$. These known results are derived by elementary combinatorial methods without appeal to the Lagrange formula, which is then obtained as a byproduct. This approach unifies and extends a number of known identities involving the distributions of various kinds of random trees and random forests.