The number of (non-equal) forests on the vertex set V = {1, 2, ...,n} that contains exactly 2 connected components is given by

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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}$