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.

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

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 A363071

Adjacent sequences: A300657 A300658 A300659 * A300661 A300662 A300663

Keyword

nonn,eigen

Author

Alois P. Heinz, Jun 18 2018

Status

approved