# [seqfan] Re: Sequence of 2-rooted trees

Neil Sloane njasloane at gmail.com
Tue May 1 16:11:11 CEST 2018

Brendan,  You are right - and the sequence is A081131.  I'll add a comment.

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.
Email: njasloane at gmail.com

On Tue, May 1, 2018 at 1:24 AM, Brendan McKay <Brendan.McKay at anu.edu.au>
wrote:

> Hi Neil,
>
> It is the number of labelled trees n^(n-2) times the number of adjacent
> labels,
> which is the number of edges n-1.
>
> And without the requirement of adjacency, it should be n^(n-2) *
> binom(n,2).
>
> In general I don't see what rooting a labelled structure does except choose
> some labels.
>
> Cheers, Brendan.
> On 1/5/18 3:00 pm, Neil Sloane wrote:
>
> For labeled birooted trees where the two roots are adjacent, I get the
> number to be (n-1)*n^(n-2), which is A053506.There is a fairly simple
> recurrence which
>
>
> 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.
> Email: njasloane at gmail.com
>
>
> On Mon, Apr 30, 2018 at 11:00 PM, Brendan McKay <Brendan.McKay at anu.edu.au>
> wrote:
>
>> I agree with
>>
>> 0, 1, 2, 6, 15, 43, 116, 329, 918, 2609
>>
>>
>> 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 <https://maps.google.com/?q=11+South+Adelaide+Avenue,+Highland+Park,+NJ+08904,+USA&entry=gmail&source=g>.
>> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
>> Email: njasloane at gmail.com
>>
>>
>> On Mon, Apr 30, 2018 at 9:41 AM, Richard J. Mathar <mathar at mpia-hd.mpg.de> <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/
>>
>>
>