lessOrEqualReverse(P,r) = { \\ Is the promenade P lexicographically less than or equal to its reverse?
local(B, x, y, z); B = Vec(0, r); z = 0;
forstep(i = #P, 1, -1,
y = B[x = P[i]];
if(y==0, B[x] = y = z = z+1);
if(y < P[#P+1-i], return(-1)); \\ Return No as an answer
if(y > P[#P+1-i], return(1)) \\ return Yes (less than) as an answer
);
return(0) \\ return Yes (equal) as an answer
}
enumeratePromenades(P, A) = { \\ P is a promenade to extend, A holdholds a list of neighbours for every node in P
local(z, Az); z = P[#P]; \\ z is the current last node in P
if(z>1 && lessOrEqualReverse(P,#A)>=0, C[#P-1,#A-1]++); \\ Count the current promenade if it doesn't end with the starting node 1 and is preferred to its reverse
if(#P>N, return); \\ Don't go any deeper if max length has been reached
Az = A[z]; \\ Current neighbour list of last node
for(i = 1, #Az,
enumeratePromenades(concat(P, Az[i]), A) \\ Extend P with every known neighbour of its last node
);
A[z] = concat(Az, #A+1); \\ Temporarily add a newborn node to z's neighbour
enumeratePromenades(concat(P, #A+1), concat(A, [[z]])) \\ Extend P with the newborn node
}
N = 20; C = matrix(N,N);
enumeratePromenades([1],[[]])
C
The idea is to label the start point with 01, the next point on the promenade with 12, then the next with 01 or 23 according to whether the promenade goes back or reach a new third point, and so on. Then it'sit is only a matter of counting corresponding finite sequences of integers.
This seems to be highly related to https://oeis.org/A186952 because when -- unlike what you want -- you distinguish the start point from the endpoint and further allow both to possibly be the same, you get the sequence