login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A300660 Number of unlabeled rooted phylogenetic trees with n (leaf-) nodes such that for each inner node all children are either leaves or roots of distinct subtrees. 37
0, 1, 1, 2, 3, 6, 13, 30, 72, 182, 467, 1222, 3245, 8722, 23663, 64758, 178459, 494922, 1380105, 3867414, 10884821, 30756410, 87215419, 248117618, 707952902, 2025479210, 5809424605, 16700811214, 48113496645, 138884979562, 401645917999, 1163530868090 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

From Gus Wiseman, Jul 31 2018 and Feb 06 2020: (Start)

a(n) is the number of lone-child-avoiding rooted identity trees whose leaves form an integer partition of n. For example, the following are the a(6) = 13 lone-child-avoiding rooted identity trees whose leaves form an integer partition of 6.

  6,

  (15),

  (24),

  (123), (1(23)), (2(13)), (3(12)),

  (1(14)),

  (1(1(13))),

  (12(12)), (1(2(12))), (2(1(12))),

  (1(1(1(12)))).

(End)

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..2079

Wikipedia, Phylogenetic tree

Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

FORMULA

a(n) ~ c * d^n / n^(3/2), where d = 3.045141208159736483720243229947630323380565686... and c = 0.2004129296838557718008171812000512670126... - Vaclav Kotesovec, Aug 27 2018

EXAMPLE

:   a(3) = 2:        :   a(4) = 3:                      :

:      o       o     :        o         o        o      :

:     / \     /|\    :       / \       / \     /( )\    :

:    o   N   N N N   :      o   N     o   N   N N N N   :

:   ( )              :     / \       /|\                :

:   N N              :    o   N     N N N               :

:                    :   ( )                            :

:                    :   N N                            :

From Gus Wiseman, Feb 06 2020: (Start)

The a(2) = 1 through a(6) = 13 unlabeled rooted phylogenetic semi-identity trees:

  (oo) (ooo)     (oooo)         (ooooo)             (oooooo)

       ((o)(oo)) ((o)(ooo))     ((o)(oooo))         ((o)(ooooo))

                 ((o)((o)(oo))) ((oo)(ooo))         ((oo)(oooo))

                                ((o)((o)(ooo)))     ((o)(oo)(ooo))

                                ((oo)((o)(oo)))     (((o)(oo))(ooo))

                                ((o)((o)((o)(oo)))) ((o)((o)(oooo)))

                                                    ((o)((oo)(ooo)))

                                                    ((oo)((o)(ooo)))

                                                    ((o)(oo)((o)(oo)))

                                                    ((o)((o)((o)(ooo))))

                                                    ((o)((oo)((o)(oo))))

                                                    ((oo)((o)((o)(oo))))

                                                    ((o)((o)((o)((o)(oo)))))

(End)

MAPLE

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

      add(b(n-i*j, i-1)*binomial(a(i), j), j=0..n/i)))

    end:

a:= n-> `if`(n=0, 0, 1+b(n, n-1)):

seq(a(n), n=0..30);

MATHEMATICA

b[0, _] = 1; b[_, _?NonPositive] = 0;

b[n_, i_] := b[n, i] = Sum[b[n-i*j, i-1]*Binomial[a[i], j], {j, 0, n/i}];

a[0] = 0; a[n_] := a[n] = 1 + b[n, n-1];

Table[a[n], {n, 0, 31}] (* Jean-François Alcover, May 03 2019, from Maple *)

ursit[n_]:=Prepend[Join@@Table[Select[Union[Sort/@Tuples[ursit/@ptn]], UnsameQ@@#&], {ptn, Select[IntegerPartitions[n], Length[#]>1&]}], n];

Table[Length[ursit[n]], {n, 10}] (* Gus Wiseman, Feb 06 2020 *)

CROSSREFS

Cf. A000081, A004111, A141268, A289501, A301467.

Cf. A000669, A001678, A005804, A292504, A300660, A316653, A316654, A316656.

The locally disjoint case is A316694.

Cf. A276625, A306200, A319312, A331679, A331686, A331875.

Sequence in context: A052937 A005554 A316766 * A077212 A076836 A296531

Adjacent sequences:  A300657 A300658 A300659 * A300661 A300662 A300663

KEYWORD

nonn,eigen

AUTHOR

Alois P. Heinz, Jun 18 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 17 02:26 EDT 2021. Contains 343059 sequences. (Running on oeis4.)