A problem Idea

Find the number of trees with K nodes in a given graph/tree with N nodes.

I am not sure if adding any restriction to the type of graph/tree we can reduce the time complexity .

Any suggestions?

I am thinking on the lines of having a restriction on K and then storing results for {1,2,3…K} node subtrees for each node and then propagating the solution.

I feel like I have seen this problem, I am not sure though. Can some one else comment?

Ya. The problem looks standard for me too.