how to compute the probability that a random graph has two components? [closed]

Question

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

Answer 1

There are several alternative derivations. It seems that in the derivation you are following, the first component is defined as the component of the node 1, so if this component has size $k$, then only $k-1$ additional nodes from $\{2,\ldots,n\}$ must be chosen for this component.