I'll answer a question raised in the comments:
Problem: Count the number of induced trees of size $k$.
According to this paper by Erdös, Saks and Sos, it is NP-hard to decide given a graph $G$ and an integer $k$, if $G$ contains an induced tree of size $k$. So, it's probably pretty damn hard to count them. Apparently, it remains NP-hard even for bipartite graphs.