Given a complete graph $(V,E)$ with $n$ vertices $V$ and walks $p \in V^{l+1}$ of length $l$. We say the edges of walks $p$ are the multiset

$$ e_p = \{ (p_i,p_{i+1}) \mid 1 \leq i \leq l \}. $$ Also the frequency of vertex $v \in V$ in walk $p$ is $p[v] = |\{ i \mid p_i = v \}|$. The frequency of all vertices $f_p \in \mathbb{N}^n$ in walk $p$ is then given by $$ f_p = [ p[v_1], p[v_2], \dots, p[v_n] ]. $$

Now, two walks $p$ and $q$ are called edge-invariant if $f_p = f_q$ and $e_p = e_q$. How many different walks of length $l$, which are not edge-invariant, exist? More precisely, i.e., $$ max_{P \subset V^{l+1}} | \{ P \mid \forall p, q \in P: e_p \neq e_q \textrm{ or } f_p \neq f_q \textrm{ for } p \neq q \}|. $$

For example, $n = 2$, it's $4, 8, 14, 22, 32, 44, 58, 74, 92, 112, 134, 158$ for $l = 1,\dots,12$. Specifically for $l = 3$, out of the 16 possible walks, two are edge-invariant: $$ e_{[1,1,2,1]} = e_{[1,2,1,1]} \textrm{ and } e_{[2,2,1,2]} = e_{[2,1,2,2]}. $$

For $n = 3$, it's given here as $9, 27, 75, 186, 414, 840, 1578, 2784, 4662, 7476, 11556$ for $l = 1,\dots,11$.

It seems to be related to k-abelian equivalence classes, where the general problem seems to be rather difficult, but maybe the 2-abelian cases is simpler?

6more comments