The number of (non-equal) forests on the vertex set V = {1, 2, ...,n} that contains exactly 2 connected components is given by The number of (non-equal) forests on the vertex set V = {1, 2, ...,n} that contains exactly 2 connected components is given by $\sum_{k=1}^{n-1} {n-1 \choose k-1} k^{k-2} (n-k)^{n-k-2}$.
I am unsure how to approach this question.
Could someone guide me through the proof?
If G is a spanning tree and it is disconnected then I know it is a spanning forest.
Also, I know by Cayley's thm that there are $n^{n-2}$ nonequal tree on a vertex set V = {1, 2, ...,n} which is where i'm assuming the $k^{k-2}$ comes from but I do not understand where the rest of it is coming from. 
 A: HINT: The forest must consist of exactly two trees. Partition $V$ into two disjoint non-empty subsets, $V_0$ and $V_1$, and let $V_0$ be the subset containing the vertex $1$. $V_0$ and $V_1$ will be the vertex sets for the two trees. Let $k=|V_0|$. 


*

*Since we’ve decided that vertex $1$ will be in $V_0$, how many ways are there to choose the rest of $V_0$?  

*Then how many different trees are there with vertex set $V_0$, and how many with vertex set $V_1$?  

*What are the possible values of $k$?


Then put the pieces together.
A: Let $k$ be the number of vertices in the component containing vertex $1$.  Then $1\le k\le n-1$.  For each such $k$,


*

*choose the other $k-1$ of $n-1$ available vertices to be in the same component as $1$;

*choose one of the $k^{k-2}$ possible trees on these vertices;

*choose one of the possible trees on the other $n-k$ vertives.


See if you can fill in the details.
A: There are $\sum_{k=1}^{n-1}\binom{n-1}{k-1}$ ways to select the two components. This is because to avoid overcounting we can fix a vertex $v$ and choose the other vertices which are going to be in its component.
Once the components have been selected, since the component containing $v$ has $k$ vertices there are $2^{k-2}$ spanning trees that component could have. The other component has $n-k$ vertices and thus it could have $2^{n-k-2}$ spanning trees.
Thus the answer is $\sum_{k=1}^{n-1}\binom{n-1}{k-1}2^{k-2}2^{n-k-2}$
