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?
 A: 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]
