# An approximation for the number of subtrees of a tree

Let $T$ be a labeled tree with the root $v$, such that:

$(i)$ The height of the tree is $x$,

$(ii)$ the degree of the vertex $v$ is $y-2$,

$(iii)$ the degree of each vertex, except the leaves and the vertex $v$ is $y$.

Let $T(x,y)$ be the the set of subtrees of $T$ such that:

$(i)$ each subtree in $T(x,y)$ has exactly $x+1$ vertices, and

$(ii)$ each subtree in $T(x,y)$ has the vertex $v$.

There are multiple $T(x,y)$ satisfying $(i)–(iii)$. I take the largest such $T(x,y)$. Can one find an approximation for $|T(x,y)|$?

Example. $|T(2,3)|=2$, $|T(3,3)|=5$.

• Is it intentional that there are multiple $T$ satisfying (i)–(iii)? If you take the largest such $T$ then I would be optimistic that somebody could work out at least the asymptotics using generating functions. Feb 1 '17 at 10:06
• I am looking for the size of the largest one. I edited the problem. Feb 1 '17 at 18:04

For $y=3$, one takes one branch of a (otherwise full) binary tree of height x and finds a recurrence of the form T(x,y)= sum over z from 1 to x-1 of T(z,3)*T(x-1-z,3) , which smells to me like a recurrence for Catalan numbers, which would give a correspondence T(x,3) is the (x-c)th Catalan number for some small constant c. I have not done the computations however.

A more general recurrence for larger y is like the sum over all partitions (p_1,...,p_k) of x-1 into k=y-1 parts (where some of the p_i could be zero) of T(p_1,y)*...*T(p_k,y ), except that there is an extra wrinkle in going from the x situation to x-1. In the binary case the lone branch from the root helped us set up the recursion nicely, whereas for y larger than 3 we have to worry about the (out-) degree change from y-2 to y-1, so the actual recursion looks like the above but may be the product of something other than T's. There may be a generalization of Catalan numbers worked out for this, which you might find after calculating some small examples.

Gerhard "OEIS Is Your Friend Here" Paseman, 2017.02.01.

As a suggestion:

Define $F(x,y,z)=\#$ subtrees of $T$ which has $v$ and the size equal to $z$.

So you need to approximate $T(x,y)=F(x,y,x+1)$

But you can calculate a recursive function for it with $z_i$s have sum equal to $x+1$