Consider a random undirected graph $G(n, p)$, with $n$ vertices and each edge is added independently with probability $p$.
The goal is to find the expected number of vertex-pairs without any simple path (length $\leq k$) in between.
Here is how I think about $k = n$: The expected number of isolated vertices is $n (1-p)^{n-1}$. Therefore the expected number of non-isolated vertices is $n(1-(1-p)^{n-1})$. Hence the expected number of vertex pairs WITH a simple path in between is $$ A= {n(1-(1-p)^{n-1}) \choose 2} $$ And the expected number of vertex pairs without a simple path in between is $$ {n \choose 2} - A $$
For the case of $k< n$, maybe I can say this: The expected number of non-isolated vertices is the same. The expected number of vertices which have (at least) a path of length at most $k$ is: $$ A(k)= {n(1-(1-p)^{n-1}) \choose 2} \sum_{l=1}^k {n(1-(1-p)^{n-1}) \choose l-1} (l-1)!p^l $$ And the expected number of vertex pairs without a simple path in between is $$ {n \choose 2} - A(k) $$
Any comments on my solution?