# Traces and closed walks that do not close before their time

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?

I don't think so. Let $$a_k$$ be the number of paths of length $$k$$ starting and ending at a particular vertex, and let $$b_k$$ be the number of such paths who return to their origin for the first time at step $$k$$. For convenience set $$a_0=1$$ and $$b_0=0$$. Then for $$n\geq 1$$ we have $$a_n = \sum_{k=0}^n b_k a_{n-k}$$.
Let $$A_v(x),B_v(x)$$ be the associated generating functions, depending on the chosen vertex. The identity above is $$A_v-1=A_vB_v$$ and hence $$B_v = 1-1/A_v$$.
Now $$\sum_v A_v(x)=\sum_{k\geq 0} \mathrm{Tr}(A^k)x^k = \mathrm{Tr}\left(\sum_{k\geq 0} A^k x^k\right)$$ and we conclude that $$\sum_v A_v(x) = \mathrm{Tr} \left((\mathrm{Id}-Ax)^{-1}\right)\,,$$ but this can't lead to a simple formula for $$\sum_v B_v(x)$$ in general (you will get a formula when the graph is vertex-transitive).
[Editing to add: counting self-avoiding walks is much harder. Even the asymptotic number of self-avoiding walks in $$\mathbb{Z}^d$$ is not known precisely, see https://www.math.ubc.ca/~slade/spa_proceedings.pdf]