Let $G(N, p)$ be a directed Erdős–Rényi random graph with edge probability $p$. Let $W_k$ denote the number of walks (potentially with repeated vertices, or repeated edges) of length $k$ beginning at a fixed vertex $i$ and terminating at a fixed vertex $j$. What is the expected number of walks, $\mathbb E [W_k]$?
From this question, I know the expected number of paths is $(N!/(N-k)!)p^k.$
I think we can write $\mathbb E [W_k] = \sum_{n=1}^k p^k V_k$, where $V_k$ counts the number of walks with $k$ unique edges in the complete graph with $N$ vertices. Is there a nice formula for $V_k$?
An alternate way to phrase this problem is that I am looking for the expected value of $(A^k)_{ij}$, where $A$ is $N\times N$ matrix with Bernoulli random entries.