[seqfan] Re: Enumerating DFS on multigraphs

[Li-yao Xia]

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'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.

de Bruijn indices offer a mechanical way to encode back edges which
is convenient for implementation. 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,
Li-yao

On 03/02/2017 06:40 AM, Antti Karttunen wrote:
> I mean, even though your graph-theoretical 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 Li-Yao,
>>>>
>>>> Your problem ( http://list.seqfan.eu/pipermai
>>>> l/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
>>
>>

-------------- next part --------------
1 edge:

o
|
*

2 edges:

o
|
o
|
o

o   o
 \ /
  o

o
|\1
|/
*

3 edges:

o
|
o
|
o
|
*

o   o
 \ /
  o
  |
  *

o
|
o   o
 \ /
  *

    o
    |
o   o
 \ /
  *

o o o
 \|/
  *

 o
 |\1
 |/
 o
 |
 |
 *

 o
 |
1|
 o
 |\2
 |/
 *

 o
 |
2|
 o
 |\1
 |/
 *

 o
 |\1
 | |
 o |
 | |
 |/
 *

o     o
 \   /|1
  \ //
   *

o 1   o
 \\  /
  \|/
   *

 o
 |\\1,2
 |//
 *