I'll consider a simpler graph: one that has distinct loops of lengths \$$a_1, ... a_k\$$. Then the number of paths with length \$$n\$$ that start and end at the chosen node is the number of ways to pick nonnegative integer coefficients \$$b_i\$$ such that:
\$$n=\sum_i^k a_i \cdot b_i\$$