MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 Fixed a minor typo.

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, Thm 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/(2ed)^{k-1} 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.

show/hide this revision's text 1

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, Thm 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/(2ed)^{k-1} \to 0$ in expectation (or in probability), perhaps assuming that $B$ has 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.