[seqfan] Re: Enumerating DFS on multigraphs

[Antti Karttunen]

On Thu, Mar 2, 2017 at 11:23 AM, Antti Karttunen <antti.karttunen at gmail.com>
wrote:

>
> Could you prepare an illustration for cases n=1 .. 3 edges (or at least
> for the 12 instances with 3 edges)? That could be a very helpful attachment
> to A258173, after it has been proved that it enumerates also your trees.
>
> Best regards,
>
> Antti
>
>
> On Thu, Mar 2, 2017 at 10:56 AM, Antti Karttunen <
> antti.karttunen at gmail.com> wrote:
>
>>
>> Dear Li-Yao,
>>
>> Your problem ( http://list.seqfan.eu/pipermail/seqfan/2017-March/017312.
>> html ) is very interesting.
>>
>> Just now, I'm wondering whether I have got all the parameters correctly.
>> Clearly, the A000108(n) rooted general trees give always a subset of
>> solutions, namely, those DFS-"scans" with no backlinks,
>> e.g. for graphs of three edges, those trees no 4-8 I have illustrated
>> with grude ASCII graphics in https://oeis.org/A179752
>> (The orientation of up-links is important also in your case, isn't it?)
>>
>> But for DFS's with at least one back-link, I only manage to find these
>> ones:
>>
>> E.g., if we indicate a pair of vertices with an immediate back-loop from
>> the upper vertex to the lower as (), then we
>> can add that on the top of a single edge, or below it, or at the left
>> side, or the right side of a single edge, as
>> \() or ()/, and that makes four in total. Then we can have two vertices
>> with one edge going up and two back-edges coming down, and also we can have
>> three vertices stacked on the top of each other as:
>> o
>> |
>> o
>> |
>> o
>>
>> with a single back-edge coming from the top-vertex to the bottom-vertex
>> (root).
>> And that makes six more in total, altogether 5+6 = 11, so I'm still
>> missing one example from your count of 12.
>> Which one it is?
>> (The orientation of back-links in relation to up-links is not important,
>> I guess? Or?)
>>
>>
>> Best regards,
>>
>> Antti
>>
>>
>

I think I see it now:

Because of this definition:

data EdgeB = TreeB TreeB | BackB Integer

your program counts this depth-first-traversal with backlinks twice:

|
()

(root at the bottom)

that is, it considers either the left hand edge ( or the right hand edge )
to be the back-link (and the other one respectively the "uplink"). Is this
the intended behaviour?

Now, if this is intended (although I'm not sure how it can be justified
"graphically"), then I guess the following simple bijection with the
original interpretation of https://oeis.org/A258173 works:

For any leaf at height n (with root at 0) in the general rooted oriented
trees (that is, a peak in Dyck path interpretation), one can either leave
that branch intact, or delete that leaf-vertex and draw from its immediate
ancestor vertex (at height n-1, i.e. one immediately below if the root is
drawn at the bottom) a back-link to any of the n-1 ancestor vertices (at
levels n-2 .. 0). So there is n choices what to do for each leaf at level
n, and this can be done independently of any other leaf-branches, thus the
multiplication in formula of A258173.

On the other hand, if this was a mistake in your Haskell-definition, then
it is very interesting mistake.


Best regards,

Antti