[seqfan] Re: Sequence of 2-rooted trees
Brendan McKay
Brendan.McKay at anu.edu.au
Tue May 1 07:24:28 CEST 2018
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
> leads to the proof.
>
>
> 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 <mailto:njasloane at gmail.com>
>
>
> On Mon, Apr 30, 2018 at 11:00 PM, Brendan McKay
> <Brendan.McKay at anu.edu.au <mailto:Brendan.McKay at anu.edu.au>> wrote:
>
> 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 <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.
>> Phone: 732 828 6098; home page:http://NeilSloane.com
>> Email:njasloane at gmail.com <mailto:njasloane at gmail.com>
>>
>>
>> On Mon, Apr 30, 2018 at 9:41 AM, Richard J. Mathar<mathar at mpia-hd.mpg.de> <mailto: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