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

Neil Sloane njasloane at gmail.com
Tue May 1 07:00:13 CEST 2018

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/
>
>