Let a "promenade" on a tree be a walk going through every edge of the tree at least once, and such that the starting point and endpoint of the walk are distinct. What we mean by isomorphic promenades should be clear (in particular, the underlying trees have to be isomorphic). What is the total number $N(l,r)$ of promenades (up to isomorphism) of length $l$ with $r$ distinct edges (letting the underlying tree vary)?
$\begingroup$
$\endgroup$
3
asked Aug 11, 2018 at 5:18
-
1$\begingroup$ Rather than presuming clarity about ismorphism, it might be better to assume a sufficiently large and sufficiently branching underlying tree, and count the isomorphic "pre-" promenades on this big tree, and then (since you are letting the tree vary in your version) just worry about those length l r-edge walks which do (and those that do not) end where they start. The current formulation places too much emphasis on the image of a pre-promenade for this type of enumeration. My suggestion may already appear in the literature. Gerhard "I'll Walk Where I Want" Paseman, 2018.08.11 $\endgroup$– Gerhard PasemanCommented Aug 11, 2018 at 15:02
-
1$\begingroup$ Actually, I see some ambiguity already, as I do not know if isomorphism of promenades should preserve the starting point (or if a reversal of a promenade p can be isomorphic to p). So let the big tree be infinite and appropriately transitive, and the isomorphism of the promenade can be derived from a big tree isomorphism, and you can choose later to fix the starting point or not. Gerhard "Destination May Be Important Too" Paseman, 2018.08.11. $\endgroup$– Gerhard PasemanCommented Aug 11, 2018 at 15:14
-
$\begingroup$ For me, an isomorphism of promenades need not preserve the starting point, but reversal is not necessarily an isomorphism. $\endgroup$– H A HelfgottCommented Aug 11, 2018 at 20:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
In case you find it useful here is a simple computer enumeration for $\ell,r\le 20$ $$ \begin{array}{ c|r|r*{19}{r}} \ell\backslash r& \sum & 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\ \hline 1& 1& 1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 2& 1& 0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 3& 3& 1&1&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 4& 4& 0&1&2&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 5& 12& 1&3&5&2&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 6& 22& 0&3&7&8&3&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 7& 61& 1&7&20&18&11&3&1&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 8& 122& 0&4&24&41&33&15&4&1&0&0&0&0&0&0&0&0&0&0&0&0\\ 9& 355& 1&15&69&106&93&47&19&4&1&0&0&0&0&0&0&0&0&0&0&0\\ 10& 765& 0&10&74&192&227&161&71&24&5&1&0&0&0&0&0&0&0&0&0&0\\ 11& 2243& 1&31&221&516&632&464&249&94&29&5&1&0&0&0&0&0&0&0&0&0\\ 12& 5020& 0&16&222&800&1334&1288&815&374&129&35&6&1&0&0&0&0&0&0&0&0\\ 13& 14951& 1&63&677&2260&3732&3665&2522&1290&530&163&41&6&1&0&0&0&0&0&0&0\\ 14& 34599& 0&36&655&3242&7080&8902&7325&4364&1992&736&211&48&7&1&0&0&0&0&0&0\\ 15& 103641& 1&127&2019&9282&20087&25322&21704&13836&7053&2903&986&258&55&7&1&0&0&0&0&0\\ 16& 246070& 0&64&1902&12578&35447&55860&57304&42202&23895&10967&4157&1301&321&63&8&1&0&0&0&0\\ 17& 741510& 1&255&5923&36592&101567&160201&167476&128416&77918&38912&16377&5734&1675&383&71&8&1&0&0&0\\ 18& 1800739& 0&136&5513&48097&170563&330313&409966&362207&244779&133712&61152&23814&7803&2131&463&80&9&1&0&0\\ 19& 5451731& 1&511&17206&140476&492009&953828&1197472&1083274&764487&443648&218859&92624&33690&10342&2663&542&89&9&1&0\\ 20& 13499887& 0&256&15879&180845&799195&1873028&2765328&2869554&2260169&1430391&758236&345860&136814&46726&13559&3296&641&99&10&1\\ \end{array} $$
I used the following basic recursive program in Pari/GP and let it run for 4 minutes :
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 holds 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 1, the next point on the promenade with 2, then the next with 1 or 3 according to whether the promenade goes back or reach a new third point, and so on. Then it 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
$\sum_r = 1, 1, 2, 4, 9, 20, 48, 113, 282, 689, 1767, 4435, 11616, 29775, 79352, 206960, 559906, 1482188, 4064235, 10901289, 30265366$
for $0 \le \ell \le 20$, which is the mentioned oeis sequence.
answered Aug 13, 2018 at 16:00