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$.



An approximation for the number of subtrees of a tree
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.


