This question is an example in the book Introduction to Probability Models 11th edition (Sheldon M.Ross). 3.6.2 A random graph:
A graph has $V$ nodes and a set $A$ of pairs of nodes in $V$ called arcs. $V = \{1,2,...n\}$ and $A = \{(i,X(i), i=1,...,n\}$. The probability that node $i$ is connected to node $j$ is:
$P\{X(i)=j\}=\frac{1}{n}, j=1,2,...,n$
If from each node $i$, we select at random ONE of the $n$ nodes (including $i$ itself), what is the probability the graph is connected (there is a path between each pair of the $\binom{n}{2}$ nodes)?
I understand the proof of this part that this probability is: $P\{graph\ is\ connected\} \approx\sqrt{\frac{\pi}{2n(-1)}}.$
In the second part, we want to calculate the probability that there are 2 components in the random graph. Say nodes $1,2,3,...,k$ is connected, and nodes $k+1,...,n$ is connected. Let $C$ denotes the number of connected components. $P_n(i)=P\{C=i\}$.
To calculate $P_n(2)$, we need to use:
$P\{X(i)\in\{1,2,...,k\}, for\ all\ i=1,...,k\}=\left(\frac{k}{n}\right)^k$
$P\{X(i)\in\{k+1,...,n\}, for\ all\ i=k+1,...,n\}=\left(\frac{n-k}{n}\right)^{n-k}$
$P\{nodes\ 1,2,3,...,k\ form\ a\ connected\ subgraph\}=P_k(1)$
$P\{nodes\ k+1,...,n\ form\ a\ connected\ subgraph\}=P_{n-k}(1)$
So the point I DON'T understand is: because there are $\binom{n-1}{k-1}$ ways of choosing a set of $k-1$ nodes from the nodes $2$ through $n$, we have:
$P_n(2)=\sum\limits_{k=1}^{n-1}\binom{n-1}{k-1}\left(\frac{k}{n}\right)^k\left(\frac{n-k}{n}\right)^{n-k}P_k(1)P_{n-k}(1)$
Why we choose $k-1$ from $n-1$ rather than choose $k$ from $n$?
Because you are choosing the other $k-1$ nodes to share a component with node $1$.
$k$ is not the number of nodes in "one of the components". After all, there are two components, so which one would $k$ represent? Instead, $k$ is the number of nodes in the component containing node $1$. And since you already know that node $1$ is in that component, you only need to choose $k-1$ nodes to be its compatriots.