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