Number of Complete N-ary Subtrees on Galton-Watson Family Trees

We associate with a Bienaymé-Galton-Watson branching process a family tree rooted at the ancestor. For a positive integer , define a complete -ary tree to be the family tree of a deterministic branching process with offspring generating function . We study the random variables and counting the number of disjoint complete -ary subtrees, rooted at the ancestor, and having height and , respectively. Dekking (1991) and Pakes and Dekking (1991) find recursive relations for and involving the offspring probability generation function (pgf) and its derivatives. We extend their results determining the probability distributions of and . It turns out that they can be expressed in terms of the offspring pgf, its derivatives, and the above probabilities. We show how the general results simplify in case of fractional linear, geometric, Poisson, and one-or-many offspring laws.