# Counting subtrees of a random tree (“random Catalan numbers”)

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.

-
For the case where $B$ has Poisson distribution with mean $d$, maybe it's possible to do something by comparing to the random graph $G(n,d/n)$? The expectation seems easier to compute in the graph case than the tree (roughly $n^{k−1}/(k-1)!$ choices for the vertices including your root, $k^{k-2}$ choices for the trees on those vertices, each occurring with probability $(d/n)^{k−1}$, giving a product which grows exponentially in $k$ for fixed $d$), and it feels like their behaviors should be similar if we let n be much larger than k. –  Kevin P. Costello Jun 1 '11 at 14:45

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.

-
Can you say a few words about how you obtained the formula $\prod_{v\in\theta} q_{d_v}$? Thanks! –  Konstantinos Panagiotou Jun 6 '11 at 9:31
This looks like it should work in fair generality, whenever $Q(z)$ behaves reasonably. Vertex weights might make the computations a little simpler than edge weights, I'll see. Thanks for the suggestion, Omer -- when I get around to working out some details I'll post an update. –  Louigi Addario-Berry Jun 7 '11 at 17:56