Number of induced subforests in a a tree

Question

Whilst working on my master thesis I would find it usefull if the number of induced subforests (up to isomorphism) of a tree of size $n$ would be bound by a polynomial in $n$. I've got no good way to prove this. Does anyone have any hints/ ideas on how to prove/disprove this? Thanks a lot in advance

Answer 1

If $p(n)$ is the partition function - the number of ways to write $n$ as a sum of positive integers, ignoring order - then the $n$-vertex path has at least $p(\lceil n/2\rceil)$ induced subforests. If $a_1 \le a_2 \le \dots \le a_k$ is a partition of $\lceil n/2\rceil$, there is an induced subforest whose components are paths with $a_1, a_2, \dots, a_k$ vertices. (We only go up to $\lceil n/2\rceil$, because in order to obtain this subforest, we have to skip $k-1$ vertices between its components.)

According to Wikipedia, we have $$p(n) \sim \frac1{4n\sqrt 3} \exp\left(\pi \sqrt{\frac{2n}{3}}\right),$$ so the number of induced subforests of the $n$-vertex path grows faster than polynomially.