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&lt;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?
Your mistake is that you assume that the probability of a union of events is the sum of their probabilities. This is only true if the events are disjoint, which isn't the case here.

Your formula for the probability that there is a path of length $k$ is wrong.  Note for example that for $k=2$ your expression for $P_n(k)$ is $\frac{n-2}{2}$, which is larger than 1. Probabilities are always between zero and one.

In fact, your formula is the expected number of paths of length $k$.

When you add the probabilities together, once again you are computing an expectation. What your formula actually computes is the expected number of paths between two vertices.
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}