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

  • 1
    $\begingroup$ 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. $\endgroup$
    – Ben Barber
    Feb 1 '17 at 10:06
  • $\begingroup$ I am looking for the size of the largest one. I edited the problem. $\endgroup$ 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.