[seqfan] Re: Enumerating DFS on multigraphs
Antti Karttunen
antti.karttunen at gmail.com
Thu Mar 2 12:01:40 CET 2017
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 LiYao,
>>
>> Your problem ( http://list.seqfan.eu/pipermail/seqfan/2017March/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 48 I have illustrated
>> with grude ASCII graphics in https://oeis.org/A179752
>> (The orientation of uplinks is important also in your case, isn't it?)
>>
>> But for DFS's with at least one backlink, I only manage to find these
>> ones:
>>
>> E.g., if we indicate a pair of vertices with an immediate backloop 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 backedges coming down, and also we can have
>> three vertices stacked on the top of each other as:
>> o
>> 
>> o
>> 
>> o
>>
>> with a single backedge coming from the topvertex to the bottomvertex
>> (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 backlinks in relation to uplinks 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 depthfirsttraversal with backlinks twice:

()
(root at the bottom)
that is, it considers either the left hand edge ( or the right hand edge )
to be the backlink (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 leafvertex and draw from its immediate
ancestor vertex (at height n1, i.e. one immediately below if the root is
drawn at the bottom) a backlink to any of the n1 ancestor vertices (at
levels n2 .. 0). So there is n choices what to do for each leaf at level
n, and this can be done independently of any other leafbranches, thus the
multiplication in formula of A258173.
On the other hand, if this was a mistake in your Haskelldefinition, then
it is very interesting mistake.
Best regards,
Antti
More information about the SeqFan
mailing list