Consider $K_n$, which is the complete graph on $n$ vertices (every edge is present). I want to count the number of paths of length $k$ that start from vertex $1$ to vertex $2$, where repeated edges are allowed. $k$ is small compared to $n$, you can think of $k = \log(n)$ ($k$ is an asymptotic parameter that increases with $n$).
In particular, I would like to show that the number of paths of length $k$ from $1$ to $2$ that contain exactly $k-\ell$ different edges is upper bounded by order $O(n^{k-1-\ell})$. Here, the direction of an edge is unimportant, in the sense that I consider traversing the edge going from $a$ to $b$ to be the "same edge" as going from $b$ to $a$. So in a particular path, going from $a$ to $b$, then back from $b$ to $a$ counts as only traversing through one distinct edge.
Another way to look at this is to consider a sequence $(1, r_1), (r_1, r_2), \dots, (r_{k-1}, 2)$ (for notations sake let $r_0 = 1$ and $r_k = 2$). Any path can be viewed as choosing the sequence $r_i \in [n]$ arbitrarily, only under the condition that $r_i \neq r_{i+1},$ and I want to count the number of ways to choose these $r_i$ so that the cardinality of $\{ (r_i, r_{i+1})\}_{i=0}^{k-1}$ is $k-\ell$. Note that $(a,b)$ and $(b,a)$ are considered to be the same element.
Intuitively this should make sense because if you constrain a path to have only $k-\ell$ distinct edges, so that $\ell$ of the edges are "repeated," then each repeated edge should remove the number of degrees of freedom by a factor of approximately $n$. For example, if I want the edge $(r_0, r_1) = (1,3)$ to be repeated, then one way to make this constraint is to set $r_2 = 1$. If I didn't have this constraint, then there would be $n-1$ possible choices for $r_2$, but with this constraint, there is only $1$ choice, hence reducing the number of possibilities by a factor of $n$.
While this seems intuitive, I can't quite make it rigorous. I tried starting from the set of paths that pass through all different vertices (the number of such paths is upper bounded by $(n-1)^{k-1}$), and then adding in constraints one at a time to reduce the number of distinct edges. The argument was that if you try to make an edge not repeated, then you will cause one coordinate to only have like 1 option (similar to setting $r_2 = 1$ above), reducing the number of possibilities by $\approx n.$ Then if you run this argument $\ell$ times, you will have $O(n^{k-1-\ell})$ possibilities, as desired. The problem here is that sometimes if you change one coordinate, you might cause two repeated edges. For example, say $(r_0, r_1, r_2, r_3, r_4) = (1, 3, 4, 3, 5)$. Then if you change $r_2 = 1$, then suddenly you have an edge that appears 3 times instead of 2 as intended. This suggests that sometimes you only have to run this procedure fewer than $\ell$ times to get a path with $\ell$ repeated edges, which is bad because that means the order might not reduce by $n^\ell$. Of course, "most of the time" you should have to run the argument $\ell$ times, but I'm not quite sure exactly how to make it rigorous.
Any advice would be great!
Edit: One way you can try to start is notice that on a path of length $k$ with $k-\ell$ different edges, that there are at most $k-\ell-1$ vertices other than $1$ and $2$ on the path. Thus there are at most $\binom{n}{k-\ell-1}$ ways to choose the other vertices. However, the problem is that you need to order these $k+1$ vertices, which incurs another $k^k$ term. Granted, this is only about $n^{\log(\log(n))}$, but I would like to get rid of it if possible.
I take it that you want to show that for fixed $k$ and $\ell$, the number of these paths as a function of $n$ is $O\left(n^{k-\ell-1}\right)$.
The $k-\ell$ different edges form a connected subgraph of the graph. Thus, they are incident to at most $k-\ell+1$ vertices (where this bound is achieved iff the subgraph is acyclic). Two of those vertices are $1$ and $2$, so the edges are incident to at most $k-\ell-1$ other vertices.
Now, for given $k$ and $\ell$, there is a finite set of connected graphs on at most $k-\ell+1$ vertices, and for each such graph, a finite number of ways to go from $1$ to $2$ in $k$ steps. For given $n$, you get all your paths by choosing at most $k-\ell-1$ vertices in $K_n$, forming one of those graphs and traversing it in one of those ways. Thus, the number of such paths is bounded by some finite constant times $n^{k-\ell-1}$.