$S(n) = $ Number of undirected forests with $n$ vertices.
I need to find $S(n)$ recursively.
The solution is:
Remove the tree with the vertex $n$ along with all other vertices in it.
If there are $k$ vertices in the tree then order them by Cayley's formula.
The remained vertices are a forest with $n-k$ vertices. Hence:
$$S(n)=\sum_{k=1}^n \binom{n-1}{k-1}k^{k-2}S(n-k)$$
I don't understand where $\binom{n-1}{k-1}$ came from. I would love some more detailed explanation over the whole solution if possible as well.
The tree containing vertex $n$ contains $k-1$ other vertices, and they can be any $k-1$ of the $n-1$ vertices $1,2,\ldots,n-1$. Thus, for each $k$ there are $\binom{n-1}{k-1}$ ways to choose the other $k-1$ vertices of the tree containing vertex $n$, $k^{k-2}$ ways to build that tree, and $S(n-k)$ forests on the remaining $n-k$ vertices.