[seqfan] Re: Enumerating DFS on multigraphs
Antti Karttunen
antti.karttunen at gmail.com
Thu Mar 2 17:51:27 CET 2017
On Thu, Mar 2, 2017 at 3:54 PM, Liyao Xia <lysxia at gmail.com> wrote:
> Hello Antti,
>
> Thank you very much for your feedback, and the bijection! Indeed, this
> is the behavior I had in mind. Some illustrations would be a good
> idea, attached are crude ones in ASCII for n=1 to 3, where (tree and
> back) edges around some vertices are explicitly numbered, indicating
> the presence of back edges and to disambiguate the two subtle cases.
>
I guess you mean this same pair that I also meant:
o

1
o
\2
/
*
o

2
o
\1
/
*
But I wonder, shouldn't those edges be labeled instead like this:
o


o
1\2
/
*
o


o
2\1
/
*
?
Or am I missing some subtle point?
I'll make nicer pictures later if I have the time. As you mention,
> there are a couple of parameters to tweak and it would be interesting
> to see what other sequences arise out of that.
>
In graphwise context, I guess forgetting the relative position (or "side",
in relation to "uplinks") at which of the backlinks come back (towards the
root) might make sense? In that case, the above two cases would collapse to
just one, and the enumerating sequence would start as 1, 1, 3, 11, ...
In wonder if that sequence is already in OEIS?
http://oeis.org/search?q=1%2C+1%2C+3%2C+11&sort=&language=&go=Search
> de Bruijn indices offer a mechanical way to encode back edges which
> is convenient for implementation.
Does the condition "*every vertex is a binder" *specify an interesting
subset of all lambdaforms? What about the lambdaforms where not every
vertex is a binder?
Would that subset be e.g. closed regarding the application of its elements
(lambdaforms) to each other? (Maybe I should reread
http://dkeenan.com/Lambda/ )
Now, I wonder if there is a "natural" isomorphism between natural numbers
and these kinds of lambdaforms? (which are enumerated by
http://oeis.org/A258173 1, 1, 3, 12, 58, 321,)
like there are several between N and the denizens of Catalania proper?
(CC to Jon Awbrey, if this rings any bell for him...)
Best regards,
Antti
I think it's useful to help the
> intuition of people in my circle of acquaintances who are familiar with
> this concept, but otherwise there's not much to read in there from a
> purely combinatorial perspective.
>
> Cheers,
> Liyao
>
>
> On 03/02/2017 06:40 AM, Antti Karttunen wrote:
>
>> I mean, even though your graphtheoretical interpretation would result a
>> different sequence, I wonder that your "This is just like de Bruijn
>> indices
>> in lambda terms, and here every vertex is a binder" might still be useful
>> interpretation for A258173 ? Or?
>>
>> Best,
>>
>> Antti
>>
>>
>>
>> On Thu, Mar 2, 2017 at 1:01 PM, Antti Karttunen <
>> antti.karttunen at gmail.com>
>> wrote:
>>
>>
>>> 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/pipermai
>>>>> l/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