Enumerations of trees and forests related to branching processes and random walks

Enumerations of trees and forests related to branching processes and random walks

Report Number
482
Authors
Jim Pitman
Citation
In Microsurveys in Discrete Probability edited by D. Aldous and J. Propp. DIMACS Ser. Discrete Math. Theoret. Comput. Sci..
Abstract

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.

PDF File
Postscript File