The number $F(n,k)$ of forests on the vertex set $[n]$ having $k$ components and such that $1, . . . , k$ belong to distinct components? Problem: What is the number $F(n,k)$ of forests on the vertex set $[n]$ having $k$ components and such that $1, . . . , k$ belong to distinct components?
Solution given by the professor Janos Pach: Take an arbitrary tree $T$ on the vertices $v _ { 1 } , \ldots , v _ { k }$ . Any forest of $k$ components where $v _ { 1 } , \ldots , v _ { k }$ are in distinct components, together with $T$ is a tree on $n$ vertices, and vica-versa. So, we need to compute how many labeled trees on $n$ vertices contain a given labeled subtree on a given subset of $k$ vertices. Using the previous exercise, we obtain $k n ^ { n - k - 1 }$.

Previous exercice: Let $T _ { 1 } , \ldots , T _ { k }$ be trees on disjoint sets of points and $V = V \left( T _ { 1 } \right) \cup \ldots \cup V \left( T _ { k } \right) .$ What is the number of labeled trees on $V$ containing $T _ { 1 } , \ldots , T _ { k } ?$
Answer: $\left| V \left( T _ { 1 } \right) \right| \ldots \left| V \left( T _ { k } \right) \right| \cdot | V ( T ) | ^ { k - 2 }$

My question: I think I'm having difficulties in the understanding of the exercise. Is $T$ a tree with each vertices being a subtree? Are there $k$ subtrees in the forest? How manies vertices are there in a subtree? How does it relate numerically to the answer of the previous exercise?
 A: 
Is $T$ a tree with each vertex being a subtree? 

No quite; $T$ is a tree with vertex set $\{1,2,\dots,k\}$. 

Are there $k$ subtrees in the forest?

For each forest $F$ counted by $F(n,k)$, there are $k$ components, and each component is a subtree. However, there are more subtrees. For example, in the below forest, counted by $F(5,2)$, 1 - 3 is a subtree:
1 - 3 - 4

2 - 5


How many vertices are there in a subtree?

Each component in $F$ can have between $1$ and $n-k+1$ vertices. 

How does this relate numerically to the previous exercise?

It does not.

Let $T$ be any tree on the vertex set $\{1,2,\dots,k\}$; for example, you could just have $T$ be the line $1-2-\dots-k$. The idea is that, if $F$ is a forest counted by $F(n,k)$, then adding the edges of $T$ to $F$ results in a new tree with vertices $\{1,2,\dots,n\}$, let's call it $T'$, which contains $T$. Conversely, given any tree $T'$ which contains $T$, removing the edges in $T$ results in a forest with $k$ components such that $\{1,2,\dots,k\}$ are in different components. This bijection shows that $F(n,k)$ is equal to the number of trees containing $T$.
How do we use the previous exercise to count trees on $\{1,2,\dots,n\}$ containing $T$? Define $T_1, T_2,\dots,T_{n-k+1}$ as follows:


*

*$T_1$ is the tree $T$ on vertex set $\{1,2,\dots,k\}$.

*$T_2$ is a tree with no edges on the vertex set $\{k+1\}$.

*$T_3$ is a tree with no edges on the vertex set $\{k+2\}$.

*$\vdots$

*$T_{n-k+1}$ is a tree with no edges on the vertex set $\{n\}$.
Note that the union of the vertex sets for $T_1,T_2,\dots,T_{n-k+1}$ is equal to $\{1,2,\dots,n\}$, and a tree on $\{1,2,\dots,n\}$ contains all of the $T_i$ if and only if it contains $T_1=T$, since any tree will trivially contain all of the trees $T_2,T_3,\dots,T_{n-k+1}$. Using the theorem, you will get $kn^{n-k-1}$. 
