Go to main content

PDF

Description

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.

Details

Files

Statistics

from
to
Export
Download Full History
Formats
Format
BibTeX
MARCXML
TextMARC
MARC
DublinCore
EndNote
NLM
RefWorks
RIS