Probability of getting two components in a graph

Question

The following problem is an excerpt from the book Introduction to Probability Models, 10th edition, by Sheldon Ross. The origin of this problem is from $\S3.6.2$ A Random Graph, specifically after Equation (3.23) on page 147.

Here goes the problem:

Some backgrounds:

Let $C$ denote the number of connected components of our random graph, where each node has one arc emanating from it, and each component consist of several connected nodes. Let $$P_n(i) = P\{C = i\}$$ where we use the notation $P_n(i)$ to make explicit the dependence on $n$, the number of nodes. For example, $P_k(1)$ denotes the probability that there exists a connected component consists of $k$ nodes.

To obtain $P_n(2)$, the probability of exactly two components in a graph with $n$ nodes, let us first fix attention on some particular node—say, node $1$. In order that a given set of $k − 1$ other nodes—say, nodes $2, . . . , k$—will along with node $1$ constitute one connected component, and the remaining $n − k$ a second connected component, we must have

• $X(i) \in \{1, 2, . . . , k\}$, for all $i = 1, . . . , k$.
• $X(i) \in \{k + 1, . . . , n\}$, for all $i = k + 1, . . . , n$.
• The nodes $1, 2, . . . , k$ form a connected subgraph.
• The nodes $k + 1, . . . , n$ form a connected subgraph.

The probability of the preceding occurring is clearly $$ \left(\frac{k}{n}\right)^k \left(\frac{n-k}{n}\right)^{n-k} P_k(1)P_{n-k}(1) $$

and because there are ${n−1 \choose k−1}$ ways of choosing a set of $k−1$ nodes from the nodes $2$ through $n$, we have: $$P_n(2) = \sum_{k=1}^{n-1}{n−1 \choose k−1}\left(\frac{k}{n}\right)^k \left(\frac{n-k}{n}\right)^{n-k} P_k(1)P_{n-k}(1) $$.

Here are my questions:

1. Why is the probability of being in the first component as $\left(\frac{k}{n}\right)$ for each node in the second to last equation? It occurs to me the probability of two consecutive selections are dependent, i.e., if we have $k$ nodes in the first component, the probability of choosing one node, which happens to be in the component, is $\left(\frac{k}{n}\right)$, then the next node being chosen will have a probability of $\left(\frac{k-1}{n-1}\right)$ to appear in the same component.
2. Why in the last equation will we choose the $k$ nodes by first fix one and then choose the left $k-1$? Why don't we choose the $k$ nodes at once? i.e., $$P_n(2) = \sum_{k=1}^{n-1}{n \choose k}\left(\frac{k}{n}\right)^k \left(\frac{n-k}{n}\right)^{n-k} P_k(1)P_{n-k}(1) $$.

Answer 1

I think I have an answer for you.

To Question 1:

I can offer an alternative derivation that gives the same result as the book. The probability of something being true is the number of states where it is true divided by the total number of states in the universe. For a random graph there are $n^n$ possible states. If we were able to cut the universe into two pieces one with k states and one with n-k states the probability would be $\frac{k^k (n-k)^{n-k}}{n^n}$. Since we require that the two pieces be connected we multiply by the $P_i(1)$ factor for each piece giving the book's $\frac{k^k (n-k)^{n-k}}{n^n}P_k(1)P_{n-k}(1)$.

To Question 2:

The reason we choose $k-1$ nodes rather than $k$ nodes is because the book chose the first node already. This breaks the symmetry/mystery of whether you were calculating the $k$ or $n-k$ piece from the previous equation. Thus if you include the ${n}\choose {k}$ instead you will be off by a factor of two due to double counting.