I started to look at the Cayley's formula for the number of trees and the ways to prove it. I have looked at the prove by bijection and now I get it. I started to look at how to prove the Cayley's formula by recursion. I've downloaded a material in pdf and I'm trying to understand the last part "A forest of trees". What I don't understand is how did they come up with this: $$ T_{n,k} = \sum_{i=0}^{n-k}\binom{n-k}{i}T_{n-1,(k-1)+i} $$ Can anyone give me a better explanation or give me another material?
Link to the pdf material: http://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Casarotto.pdf
Put vertices 1 through $k$ in one line, and the remaining $n-k$ vertices in a line below them. Since the top $k$ vertices have to be in their own tree, there will be no edges between any of them. Consider vertex 1. It can be adjacent to $i$ of the lower vertices, where $0 \le i \le n-k$. None of those $i$ vertices will be adjacent to each other, otherwise there would be a cycle through vertex 1. None of the vertices 2 through $k$ will be adjacent to any of these $i$ vertices either, since all of the top vertices have to be in their own tree. If we delete vertex 1, we now have $n-1$ vertices. We originally had $k$ upper vertices that had to be in their own tree, now we have $k-1$ upper vertices that have to be in their own tree. The $i$ neighbors of 1 also have to be in their own tree, since there are no edges between themselves or between upper vertices 2 through $k$. Thus we have $k-1+i$ vertices that have to be in their own tree, which means we're in the $T_{n-1, k-1+i}$ case. Since this all depends on the $i$ neighbors of 1, we have to sum over all possible choices for those neighbors. There are $n-k$ neighbors to choose from, and we're choosing $i$ of them. That's where the binomial coefficient is coming from.