Let $A$ be the adjacency matrix of a graph. Then, as is well-known and trivial to show, $\mathrm{Tr} A^k$ equals the number of closed walks of length $k$.

Is there a similar way to express (a) the number of closed walks of length $k$ that do not return to their origin before $k$ steps? (b) the number of closed paths or trails of length $k$ (paths being walks that do not repeat vertices, and trails being walks that do not repeat edges)?

Let me narrow my question, in part because a closed expression may be hopeless. Say one shows that there are few closed paths of length $\leq 2 k$. Can one give an upper bound on $\mathrm{Tr} A^{2k}$, or on any related quantity, as a result?