OFFSET
1,2
COMMENTS
An edge-collision walk is a sequence of directed edges (e_1, ..., e_m) such that (i) head(e_i) = tail(e_{i+1}) for 1 <= i < m; (ii) e_1, ..., e_{m-1} are distinct; (iii) e_m = e_j for some 1 <= j < m. This counts directed trails extended by exactly one repeated-edge step summed over all starting edges.
FORMULA
a(n) = n * Sum_{k=1..n} (binomial(n-1,k-1) * A396606(k)). - Robert P. P. McKone, May 31 2026
a(n) = n * T(0, {(0,0)}) + n*(n-1) * T(1, {(0,1)}) where T(v, S) = Sum_{u=0..n-1} (1 if (v,u) in S, else T(u, S union {(v,u)})) is defined on the complete directed graph with self-loops on n vertices, where v is a vertex and S is a subset of edges.
EXAMPLE
a(1) = 1: the graph has one self-loop (0,0); the only edge-collision walk is ((0,0),(0,0)).
a(2) = 26: starting from self-loop (0,0) gives 6 walks, from (1,1) gives 6, from (0,1) gives 7, from (1,0) gives 7. Total: 6+6+7+7 = 26.
Example walks for n=2: ((0,0),(0,0)) length 2; ((0,1),(1,0),(0,1)) length 3; ((0,0),(0,1),(1,1),(1,0),(0,0)) length 5.
PROG
(Python)
def a(n):
def dfs(v, used):
t = 0
for u in range(n):
e = v * n + u
if (used >> e) & 1:
t += 1
else:
t += dfs(u, used | (1 << e))
return t
d = dfs(0, 1)
o = dfs(1, 2) if n > 1 else 0
return n * d + n * (n - 1) * o
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Arkadeep Dutta, May 25 2026
EXTENSIONS
a(7)-a(9) from Robert P. P. McKone, May 30 2026
STATUS
approved