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.



Counting subtrees of a random tree ("random Catalan numbers")
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.


