Consider a directed graph $G_n = (V, E)$ where $V = \{v_1, ..., v_n\}$ and $E=\{e_{ij}\ \forall\ i,j\in [\![1,n]\!]\}$, ie. all possible edges exist, including from a vertice to itself.
I'm trying to find an approximation (at least, the exact number would be better) on the number $f(G_n)$ of trails (walks with no repeated edges) existing in such a graph.
It's clear that the number of such paths must be divisible by $n$ by symmetry, but aside from that I have no idea how to go about it without enumerating them. If my computations are correct, $f(G_1)=1, f(G_2)=24, f(G_3)=1884$.
I have also managed to find formulas for the number of paths of length $0$, $1$, $2$, $3$ and $4$ in $G_n$ for any $n$ but I don't see any obvious generalization. Assuming $f_k(G_n)$ is the number of paths of length $k$ in $G_n$, we have:
$$f(G_n) = \sum_{k\in [\![0,n^2]\!]} f_k(G_n)$$
My calculations (if thery are right) also give the following results:
$$f_0(G_n) = n$$ $$f_1(G_n) = n^2$$ $$f_2(G_n) = n(n-1)(n+1)$$ $$f_3(G_n) = n(n-1)^2(n+2)$$ $$f_4(G_n) = n^2(n-1)(n^2 + n - 5)$$ (that last one especially may be wrong)
I would like to know if there is any known approximation or formula for either $f_k(G_n)$ or $f(G_n)$. If none of these are known, even an algorithm computing them in polynomial time (ie. without enumerating them all) would greatly help me, maybe using the multiple symmetries in the considered graphs. I have looked around but only found such algorithms for DAGs, which this clearly isn't.
Partial answer - answer only for the max length case (length $=n^2 + 1$ case), plus a loose upperbound based on that.
We take the alternate (and equivalent) view that the OP is counting the number of non-empty sequences $\in [1,n]^\infty$ where no length-$2$ subsequence $xy$ appears more than once (for any $xy \in [1,n]^2$ including possibly $x=y$). For shorthand we will call such sequences "good" sequences. Obviously the maximum length a "good" sequence can have is $n^2+1$.
A de Bruijn sequence of order $p$ on the alphabet $\{1,2,...,q\}$ is a cyclic sequence in which every possible length-$p$ sequence on the alphabet occurs exactly once as a subsequence. In the OP context, we have $p=2, q=n$. (Warning: the wikipedia article uses the parameter/variable $n$ differently! The OP uses $n$ as alphabet size, while the wikipedia article uses $n$ as the order, i.e. the length of the subsequences.)
A de Bruijn sequence (of order $2$) is equivalent to a max-length good sequence, since every length-$2$ subsequence appeared once. In the OP such a max-length sequence has length $n^2 + 1$, while the de Bruijn sequences are cyclic and have length $n^2$, but this is a difference that makes no difference: a max-length good sequence must have first and final symbols being the same (because it's an Eulerian cycle, i.e. start node = end node) so it can be written as a cyclic sequence. In short, de Bruijn (cyclic) sequences (of order $2$) are the max-length good (linear) sequences.
According to wiki, the no. of distinct de Bruijn cyclic sequences is
$$ {(q!)^{q^{p-1}} \over q^p} $$
However, this count apparently treats all sequences which are rotations as one (i.e. as non-distinct). For the OP purpose, each of the $n^2$ different start positions in a cycle are distinct linear sequences. We therefore have:
$$ f_{n^2}(G_n)=n^2 \times {(n!)^{n^{2-1}} \over n^2} = (n!)^n$$
Sanity check: the no. of length-$n^2$ sequences (not necessarily good) $= n^{n^2} = n^{n \cdot n} = (n^n)^n > (n!)^n$
CORRECTION: Originally I thought it's "obvious" that $f_k(G_n) \le f_{n^2}(G_n)$, because I thought any $(k+1)$-long good sequence (i.e. $k$-edge path) can be continued (by adding subsequent edges) into a full de Bruijn cycle (at a specific start position). I.e. I thought such a shorter path is a truncation of some de Bruijn cycle. If true, this would be a $1$-to-many map and would imply the upperbound $f(G_n) \le n^2 f_{n^2}(G_n) = n^2 (n!)^n.$
However, this is false. By exhaustive listing, we have $f_3(G_2) = 8, f_4(G_2) = 4$. What happened is that some of the shorter paths, e.g. $0010$ aka $(00, 01, 10)$, cannot be continued into a complete de Bruijn cycle (i.e., it is not a truncation of a de Bruijn cycle). In this case we "missed" the chance to use the loop $11$ and cannot add it back at the end. And of course, adding it back at some other position (and there might be a choice of many positions) would break the $1$-to-many map, and that's why $f_k > f_{n^2}$ can happen.