Counting subtrees of a random tree ("random Catalan numbers") - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T16:52:55Z http://mathoverflow.net/feeds/question/66595 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/66595/counting-subtrees-of-a-random-tree-random-catalan-numbers Counting subtrees of a random tree ("random Catalan numbers") Louigi Addario-Berry 2011-05-31T21:57:34Z 2011-06-06T18:15:28Z <p>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). </p> <p>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 <code>$N_k(T_d) = \frac{1}{k}{dk \choose k-1} &lt; (ed)^{k-1}.$</code> When $d=2$, these are simply the Catalan numbers.</p> <p>Now suppose that $\mathcal{T}$ is a Galton--Watson tree with offspring distribution $B$ and $\mathbb{E}(B)=\mu \in (1,\infty)$. </p> <blockquote> <p>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? </p> </blockquote> <p>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? </p> <p>Perhaps the problem is more combinatorially tractable if one assumes that $B$ has a Poisson distribution? This special case is interesting to me. </p> http://mathoverflow.net/questions/66595/counting-subtrees-of-a-random-tree-random-catalan-numbers/66883#66883 Answer by Omer for Counting subtrees of a random tree ("random Catalan numbers") Omer 2011-06-04T12:20:03Z 2011-06-06T18:15:28Z <p>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. </p> <p>(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$.</p> <p>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.</p> <p>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}$. </p> <p>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$. </p> <p>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.</p>