I have read this formula in a book for $c(k,k)$, the number of unicyclic connected graphs on $k$ vertices A057500, i.e. $n=m=k$.
How can one prove it? It seems that it is iterating on the length of the cycle. In addition how to prove the approximation?
$$c(k,k)=\sum_{r=3}^n {n\choose r}\frac{(r-1)!}{2}rk^{k-r-1} \sim \frac{\pi}8k^{k-0.5}$$
This is number of connected unicyclic labeled graphs. Therefore if $r$ is the length of a cycle we have $\binom{n}{r}$ ways to select $r$ vertices of cycle, $\frac{(r - 1)!}2$ ways to build a cycle on these vertices.
All we need now is the number of forests on $n$ vertices with $r$ rooted trees with given roots. It can be computed in the same way as Cayley's formula was confirmed with Prüfer code. So we can relabel vertices so that $r$ roots have numbers $n, n - 1, \ldots, n - r + 1$. Then we compute Prüfer code of forest while there is at least one edge. (Note that in case of tree we stop one step before, i. e. we compute code while there are at least two edges.) Then it is easy to see that each forest can be uniquely mapped to its Prüfer code. Each of $n - r - 1$ leaves can be adjacent to any of $n$ vertices and the last, $n - r$th leaf is adjacent to one of $r$ roots. Also no root will be deleted as leaf with minimum label, because there always is at least one other leaf. So there are $rn^{n - r - 1}$ desired forests. So $$c(k, k) = \sum_{r = 3}^n \binom{n}{r} \frac{(r - 1)!}2 rn^{n - r - 1} = \sum_{r = 3}^n \binom{n}{r} \frac{(r - 1)!}2 rk^{k - r - 1} = \sum_{r = 3}^k \frac{k!}{2(k - r)!} k^{k - r - 1}.$$
Proof of asymptotics I'll give later.
