Give a combinatorial proof of the recurrence relation

Question

Let $F_n$ be the number of forests on the vertex set $V = \{1,2,\ldots,n\}$(Thus we are counting labelled forests). Give a combinatorial proof of the recurrence relation $$F_n = \sum_{i=1} \binom{n-1}{i-1} i^{i-2} F_{n-i} $$

! A tree is a connected graph without cycles and a forest is a disjoint union of trees.

Please, help!

Answer 1

Consider the tree containing the vertex $n$. The index $i$ is the number of vertices in this tree. There are $i^{i-2}$ labeled forests with $i$ vertices and $F_{n-i}$ arrangements of the remaining $n-i$ vertices as a forest, and you can choose $i-1$ of the $n-1$ vertices other than $n$ to form the tree containing $n$.