Probability of a path of a given length between two vertices of a random graph Suppose that in  random graph $G$ on $n$ vertices any $2$ vertices can be connected by an edge with probability $\dfrac{1}{2}$, independently of all other edges.  What is the probability  $P_n(k)$ that two arbitrary vertices are connected by a simple path of length $k$, $0<k \leq n-1$?
My attempt. Fix $2$ vertices. To build a path of length $k$ we have to  choose $k-1$ vertices from the remaining $n-2$ vertices. Since order is important we can do it in $(k-1)! {n-2 \choose k-1}$  ways. There are $2^k$ configurations of the edges for a path of length $k$. Thus the probability seems to be 
$$
P_n(k)=\frac{(k-1)! {n-2 \choose k-1}}{2^k}.
$$
The sum over all path lengths, $\displaystyle \sum_{k=1}^{n-1}P_n(k)$, must equal $1$, but my calculations for small $n$ show that it is not $1$.
Where is my mistake?

It's an old question, but I was thinking about the same problem today, and here's a solution for a special case.
Let's say that there are $n+2$ total vertices and the edge-probability is $p$. Edge-probability is the probability that there exists a direct edge between two vertices. Let's say we want to find the probability that ∃ a path of length two between two vertices $x$, and $z$. 
This probability equals $1 - (1 - p^2)^n \approx np^2$ when $p$ is small enough. 
For example, if there are 100 vertices, and the edges of the graph are in a matching, i.e. the total edges in the graph equals 100, then $p = 100/(100*100)$, and the probability of length 2 path equals $0.009 \approx 0.01$. 
