I'll answer a question raised in the comments:

**Problem**: Count the number of induced trees of size $k$.

According to this [paper](http://www.renyi.hu/~p_erdos/1986-08.pdf) 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.