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?

Lets try the case k = 2. Pick any two vertices, without loss of generality you can call them 1 and 2. To construct a 2-path between them we first need to choose a third vertex, call it $i$. Clearly there are n-2 choices for $i$. Thus
$$\text{ total number of possible paths from 1 to 2 } = n-2 $$
Now for any $k$, there is an edge from 1 to $k$ with probability $p$. There is an edge from $k$ to $2$ with probability $p$ also. These are independent events, so the probability of both occuring is $p^{2}$. Thus the expected number of 2-paths from $1$ to $2$ is $p^{2}(n-2)$. and so the probability of observing one is:
$$\frac{p^{2}(n-2)}{n-2} = p^{2} $$
I suspect that in general the probability of observing a $k$ path between any two fixed vertices in such an random graph (i.e. an Erdos-Renyi random graph) is p^{k}
