The question is more combinatorial, but it is based on graph theory.
How many walks with length $k$ does an $r$-regular graph with $n$ nodes contain?
Well $r$-regular means that all nodes have $r$ neighbours, but how to determine the number of walks... I have found that $n^{\underline k}$, $n = $ number of nodes, $k = $ nodes in the walk, is one plausible formula for that purpose, but still I can`t put in $r$.
Any suggestions how to proceed?
You have $n$ choices of starting node. You then take $k-1$ steps, and at each step you have a choice of $r$ different neighboring nodes. Thus, the number of walks is $nr^{k-1}$.