cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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.

This page as a plain text file.
%I A300660 #37 Feb 07 2020 09:04:42
%S A300660 0,1,1,2,3,6,13,30,72,182,467,1222,3245,8722,23663,64758,178459,
%T A300660 494922,1380105,3867414,10884821,30756410,87215419,248117618,
%U A300660 707952902,2025479210,5809424605,16700811214,48113496645,138884979562,401645917999,1163530868090
%N 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.
%C A300660 From _Gus Wiseman_, Jul 31 2018 and Feb 06 2020: (Start)
%C A300660 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 A300660   6,
%C A300660   (15),
%C A300660   (24),
%C A300660   (123), (1(23)), (2(13)), (3(12)),
%C A300660   (1(14)),
%C A300660   (1(1(13))),
%C A300660   (12(12)), (1(2(12))), (2(1(12))),
%C A300660   (1(1(1(12)))).
%C A300660 (End)
%H A300660 Alois P. Heinz, <a href="/A300660/b300660.txt">Table of n, a(n) for n = 0..2079</a>
%H A300660 Wikipedia, <a href="https://en.wikipedia.org/wiki/Phylogenetic_tree">Phylogenetic tree</a>
%H A300660 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 A300660 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A300660 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A300660 a(n) ~ c * d^n / n^(3/2), where d = 3.045141208159736483720243229947630323380565686... and c = 0.2004129296838557718008171812000512670126... - _Vaclav Kotesovec_, Aug 27 2018
%e A300660 :   a(3) = 2:        :   a(4) = 3:                      :
%e A300660 :      o       o     :        o         o        o      :
%e A300660 :     / \     /|\    :       / \       / \     /( )\    :
%e A300660 :    o   N   N N N   :      o   N     o   N   N N N N   :
%e A300660 :   ( )              :     / \       /|\                :
%e A300660 :   N N              :    o   N     N N N               :
%e A300660 :                    :   ( )                            :
%e A300660 :                    :   N N                            :
%e A300660 From _Gus Wiseman_, Feb 06 2020: (Start)
%e A300660 The a(2) = 1 through a(6) = 13 unlabeled rooted phylogenetic semi-identity trees:
%e A300660   (oo) (ooo)     (oooo)         (ooooo)             (oooooo)
%e A300660        ((o)(oo)) ((o)(ooo))     ((o)(oooo))         ((o)(ooooo))
%e A300660                  ((o)((o)(oo))) ((oo)(ooo))         ((oo)(oooo))
%e A300660                                 ((o)((o)(ooo)))     ((o)(oo)(ooo))
%e A300660                                 ((oo)((o)(oo)))     (((o)(oo))(ooo))
%e A300660                                 ((o)((o)((o)(oo)))) ((o)((o)(oooo)))
%e A300660                                                     ((o)((oo)(ooo)))
%e A300660                                                     ((oo)((o)(ooo)))
%e A300660                                                     ((o)(oo)((o)(oo)))
%e A300660                                                     ((o)((o)((o)(ooo))))
%e A300660                                                     ((o)((oo)((o)(oo))))
%e A300660                                                     ((oo)((o)((o)(oo))))
%e A300660                                                     ((o)((o)((o)((o)(oo)))))
%e A300660 (End)
%p A300660 b:= proc(n,i) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A300660       add(b(n-i*j, i-1)*binomial(a(i), j), j=0..n/i)))
%p A300660     end:
%p A300660 a:= n-> `if`(n=0, 0, 1+b(n, n-1)):
%p A300660 seq(a(n), n=0..30);
%t A300660 b[0, _] = 1; b[_, _?NonPositive] = 0;
%t A300660 b[n_, i_] := b[n, i] = Sum[b[n-i*j, i-1]*Binomial[a[i], j], {j, 0, n/i}];
%t A300660 a[0] = 0; a[n_] := a[n] = 1 + b[n, n-1];
%t A300660 Table[a[n], {n, 0, 31}] (* _Jean-François Alcover_, May 03 2019, from Maple *)
%t A300660 ursit[n_]:=Prepend[Join@@Table[Select[Union[Sort/@Tuples[ursit/@ptn]],UnsameQ@@#&],{ptn,Select[IntegerPartitions[n],Length[#]>1&]}],n];
%t A300660 Table[Length[ursit[n]],{n,10}] (* _Gus Wiseman_, Feb 06 2020 *)
%Y A300660 Cf. A000081, A004111, A141268, A289501, A301467.
%Y A300660 Cf. A000669, A001678, A005804, A292504, A300660, A316653, A316654, A316656.
%Y A300660 The locally disjoint case is A316694.
%Y A300660 Cf. A276625, A306200, A319312, A331679, A331686, A331875.
%K A300660 nonn,eigen
%O A300660 0,4
%A A300660 _Alois P. Heinz_, Jun 18 2018