Counting subtrees of a random tree ("random Catalan numbers")

Question

Given a rooted tree $T$ and an integer $k \geq 1$, let $N_k(T)$ be the number of subtrees of $T$ containing the root and having exactly $k$ nodes (take $N_k(T)=0$ if $T$ has less than $k$ nodes).

Next, fix an integer $d \geq 2$, and let $T_d$ be the infinite $d$-ary rooted tree (every node has $d$ children). It is well-known (see, e.g. Stanley's "Enumerative combinatorics", theorem 5.3.10) that $$ N_k(T_d) = \frac{1}{k}{dk \choose k-1} < (ed)^{k-1} ~. $$ When $d=2$, these are simply the Catalan numbers.

Now suppose that $\mathcal{T}$ is a Galton–Watson tree with offspring distribution $B$ and $\mathbb{E}(B)=\mu \in (1,\infty)$.

What can be said about the behavior of $N_k(\mathcal{T})$, either in probability or in expectation, when the branching distribution $B$ may be unbounded?

In particular, it seems likely that under suitable assumptions on $B$, $N_k$ again grows exponentially in $k$. Is it the case, for example, that $N_k/(2e\mu)^{k-1} \to 0$ in expectation (or in probability), perhaps assuming that $B$ has sufficiently large exponential moments?

Perhaps the problem is more combinatorially tractable if one assumes that $B$ has a Poisson distribution? This special case is interesting to me.

Answer 1

Let $p_n$ be the offspring distribution for $B$ and define $q_n = \sum_{m\ge n} p_m (m)_n$, where $(m)_n = m!/(m-n)!$ is the descending factorial.

(new paragraph to appease MO latex scripts). Then the expected number of copies of a rooted tree $\theta$ inside the Galton Watson tree $\mathcal{T}$ is given by $\prod_{v\in\theta} q_{d_v}$ (where $d_v$ does not count the parent of $v$.

This is seen by induction on $\theta$. Given the root degree in $\mathcal{T}$ is $m$, the number of ways to select $d$ children of the root is $(m)_d$. For each of these, the expected number of ways to embed the sub-trees of $\theta$ is given by the formula (induction hypothesis). Since $\mathcal{T}$ is Galton-Watson, these are independent, and the expectation is the product of expectations.

This gives an identity $F(z) = Q(zF(z)$ for the generating function of the expected number of trees with weight $z$ for each edge. It seems that for nice $p$'s the singularity should have the same algebraic type, and so the expected number of trees in $\mathcal{T}$ grows as $C n^{-3/2} z_c^{-n}$.

In the case of the Poisson-Galton-Watson tree, it is easy to see either from the above or by staring into (probability) space that the expected number of copies of any tree $\theta$ is just $\lambda^{|\theta|}$ (still counting edges), so the expectation is just $\lambda^n C_n\sim Cn^{-3/2}(4\lambda)^n$.

Computing higher moments is probably doable in the Poisson case, but seems less fun. I will wait for additional motivation before delving into computations, but if staringinto space yields anything I'll report here.