[seqfan] Re: Sequence of 2-rooted trees

Brendan McKay Brendan.McKay at anu.edu.au
Tue May 1 05:00:27 CEST 2018


I agree with

0, 1, 2, 6, 15, 43, 116, 329, 918, 2609

and add

7391, 21099, 60248, 172683, 495509, 1424937, 4102693, 11830006,
34148859, 98686001, 285459772, 826473782, 2394774727, 6944343654

That gets up to n=24 in about 10 mins.  Several more could be added easily.

It also makes sense to use two distinguishable roots.  And it makes sense
to have separate sequences for when the two roots are adjacent or not.
So in total I suggest 6 useful sequences derived from this idea.

--------------------------------------

Incidentally, the same thing for general graphs is also absent:

Unlabelled graphs rooted at 2 indistinguishable roots (offset 1):

0, 2, 6, 28, 148, 1144, 13128, 250240, 8295664, 494367376, 53628829952

Unlabelled connected graphs rooted at 2 indistinguishable roots (offset 1):

0, 1, 3, 16, 98, 879, 11260, 230505, 7949596, 483572280, 53011686200

Brendan.

On 1/5/18 12:04 am, Neil Sloane wrote:
> Richard,  That's a surprise, a new "trees" sequence.  It does seem to be
> new - please submit it right away!
>
> Cayley studied centered trees, and bi-centered trees, but as far as I know
> he never looked at bi-rooted trees.
>
> I think "Bi-rooted trees on n nodes" would be a good name.
>
> You were looking at the case when the nodes are unlabeled, but there is
> also the labeled case, which maybe begins 0,1,9,96,... and also seems to be
> new
>
> Best regards
> Neil
>
> Neil J. A. Sloane, President, OEIS Foundation.
> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
> Phone: 732 828 6098; home page: http://NeilSloane.com
> Email: njasloane at gmail.com
>
>
> On Mon, Apr 30, 2018 at 9:41 AM, Richard J. Mathar <mathar at mpia-hd.mpg.de>
> wrote:
>
>> Is the number of 2-rooted trees (unlabeled, undirected) somewhere
>> mentioned in the OEIS? My guess is that this sequence
>> starts 0, 1, 2, 6, 15, 43, 116, 329, 918, 2609, with offset 1.
>> The concept means to mark two nodes of a tree with some (the same)
>> mark, generalizing the rooted trees  (A000081) which have only one node
>> marked.
>>
>> The 2-rooted tree has a unique path/bridge between the two nodes, which may
>> divert into branches; the other vertices are a rooted tree of one root,
>> and a rooted tree of the other root.  The middle section (bridge between
>> the roots) may be as simple as a single edge, but is in general also a
>> (2-rooted) tree.
>>
>> The forests with 2 rooted trees, column 2 in A033185, are a special
>> (limited) case, because if we connect the roots of two rooted trees by
>> a single edge, we have constructed a 2-rooted tree.
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
> --
> Seqfan Mailing list - http://list.seqfan.eu/


More information about the SeqFan mailing list