login
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

%I #37 Feb 07 2020 09:04:42

%S 0,1,1,2,3,6,13,30,72,182,467,1222,3245,8722,23663,64758,178459,

%T 494922,1380105,3867414,10884821,30756410,87215419,248117618,

%U 707952902,2025479210,5809424605,16700811214,48113496645,138884979562,401645917999,1163530868090

%N 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.

%C From _Gus Wiseman_, Jul 31 2018 and Feb 06 2020: (Start)

%C 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.

%C 6,

%C (15),

%C (24),

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

%C (1(14)),

%C (1(1(13))),

%C (12(12)), (1(2(12))), (2(1(12))),

%C (1(1(1(12)))).

%C (End)

%H Alois P. Heinz, <a href="/A300660/b300660.txt">Table of n, a(n) for n = 0..2079</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Phylogenetic_tree">Phylogenetic tree</a>

%H Gus Wiseman, <a href="https://docs.google.com/document/d/e/2PACX-1vS1zCO9fgAIe5rGiAhTtlrOTuqsmuPos2zkeFPYB80gNzLb44ufqIqksTB4uM9SIpwlvo-oOHhepywy/pub">Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F a(n) ~ c * d^n / n^(3/2), where d = 3.045141208159736483720243229947630323380565686... and c = 0.2004129296838557718008171812000512670126... - _Vaclav Kotesovec_, Aug 27 2018

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

%e : o o : o o o :

%e : / \ /|\ : / \ / \ /( )\ :

%e : o N N N N : o N o N N N N N :

%e : ( ) : / \ /|\ :

%e : N N : o N N N N :

%e : : ( ) :

%e : : N N :

%e From _Gus Wiseman_, Feb 06 2020: (Start)

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

%e (oo) (ooo) (oooo) (ooooo) (oooooo)

%e ((o)(oo)) ((o)(ooo)) ((o)(oooo)) ((o)(ooooo))

%e ((o)((o)(oo))) ((oo)(ooo)) ((oo)(oooo))

%e ((o)((o)(ooo))) ((o)(oo)(ooo))

%e ((oo)((o)(oo))) (((o)(oo))(ooo))

%e ((o)((o)((o)(oo)))) ((o)((o)(oooo)))

%e ((o)((oo)(ooo)))

%e ((oo)((o)(ooo)))

%e ((o)(oo)((o)(oo)))

%e ((o)((o)((o)(ooo))))

%e ((o)((oo)((o)(oo))))

%e ((oo)((o)((o)(oo))))

%e ((o)((o)((o)((o)(oo)))))

%e (End)

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

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

%p end:

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

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

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

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

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

%t Table[a[n], {n, 0, 31}] (* _Jean-François Alcover_, May 03 2019, from Maple *)

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

%t Table[Length[ursit[n]],{n,10}] (* _Gus Wiseman_, Feb 06 2020 *)

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

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

%Y The locally disjoint case is A316694.

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

%K nonn,eigen

%O 0,4

%A _Alois P. Heinz_, Jun 18 2018