cp's OEIS Frontend

A005804 Number of phylogenetic rooted trees with n labels.

%I A005804 M1890 #50 Nov 08 2023 17:38:18
%S A005804 1,2,8,58,612,8374,140408,2785906,63830764,1658336270,48169385024,
%T A005804 1546832023114,54413083601268,2080827594898342,85948745163598088,
%U A005804 3813417859420469410,180876816831806597500,9133309115320844870078,489156459621633161274704,27696066472039561313329018
%N A005804 Number of phylogenetic rooted trees with n labels.
%C A005804 These are series-reduced rooted trees where each leaf is a nonempty subset of the set of n labels.
%C A005804 See A141268 for phylogenetic rooted trees with n unlabeled objects. - _Thomas Wieder_, Jun 20 2008
%D A005804 Foulds, L. R.; Robinson, R. W. Enumeration of phylogenetic trees without points of degree two. Ars Combin. 17 (1984), A, 169-183. Math. Rev. 85f:05045
%D A005804 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005804 Alois P. Heinz, <a href="/A005804/b005804.txt">Table of n, a(n) for n = 1..380</a> (first 100 terms from T. D. Noe)
%H A005804 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H A005804 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A005804 Stirling transform of [ 1, 1, 4, 26, 236, ... ] = A000311 [ Foulds and Robinson ].
%F A005804 E.g.f.: -LambertW(-(1/2)*exp((1/2)*exp(z) - 1)) + (1/2)*exp(z) - 1. - _Thomas Wieder_, Jun 20 2008
%F A005804 a(n) ~ sqrt(log(2))*(log(2)+log(log(2)))^(1/2-n)*n^(n-1)/exp(n). - _Vaclav Kotesovec_, Aug 07 2013
%F A005804 E.g.f. f(x) satisfies  2*f(x) - exp(f(x)) = exp(x) - 2. - _Gus Wiseman_, Jul 31 2018
%e A005804 a(3)=8 because we have:
%e A005804   Set(Set(Z[3]),Set(Z[1]),Set(Z[2])),
%e A005804   Set(Z[3],Z[2],Z[1]),
%e A005804   Set(Set(Z[3],Z[1]),Set(Z[2])),
%e A005804   Set(Set(Set(Z[3]),Set(Z[2])),Set(Z[1])),
%e A005804   Set(Set(Set(Z[3]),Set(Z[1])),Set(Z[2])),
%e A005804   Set(Set(Z[3]),Set(Set(Z[1]),Set(Z[2]))),
%e A005804   Set(Set(Z[3]),Set(Z[2],Z[1])),
%e A005804   Set(Set(Z[3],Z[2]),Set(Z[1])).
%e A005804 From _Gus Wiseman_, Jul 31 2018: (Start)
%e A005804 The 8 series-reduced rooted trees whose leaves are a set partition of {1,2,3}:
%e A005804   {1,2,3}
%e A005804   ({1}{2,3})
%e A005804   ({1}({2}{3}))
%e A005804   ({2}{1,3})
%e A005804   ({2}({1}{3}))
%e A005804   ({3}{1,2})
%e A005804   ({3}({1}{2}))
%e A005804   ({1}{2}{3})
%e A005804 (End)
%p A005804 # From _Thomas Wieder_, Jun 20 2008: (Start)
%p A005804 ser := series(-LambertW(-1/2*exp(1/2*exp(z)-1)) + 1/2*exp(z)-1, z=0, 10);
%p A005804 seq(n!*coeff(ser, z, n), n = 1..9);
%p A005804 # Alternative:
%p A005804 with(combstruct):
%p A005804 A005804 := [H, {H=Union(Set(Z,card>=1), Set(H,card>=2))}, labelled];
%p A005804 seq(count(A005804,size=j), j=1..20);
%p A005804 # (End)
%t A005804 numSetPtnsOfType[ptn_]:=Total[ptn]!/Times@@Factorial/@ptn/Times@@Factorial/@Length/@Split[ptn];
%t A005804 a[n_]:=a[n]=If[n==1,1,1+Sum[numSetPtnsOfType[ptn]*Times@@a/@ptn,{ptn,Rest[IntegerPartitions[n]]}]];
%t A005804 Array[a,20] (* _Gus Wiseman_, Jul 31 2018 *)
%o A005804 (PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
%o A005804 b(n,k)={my(v=vector(n)); for(n=1, n, v[n]=binomial(n+k-1, n) + EulerT(v[1..n])[n]); v}
%o A005804 seq(n)={my(M=Mat(vectorv(n, k, b(n,k)))); vector(n, k, sum(i=1, k, binomial(k, i)*(-1)^(k-i)*M[i,k]))} \\ _Andrew Howroyd_, Oct 26 2018
%Y A005804 Cf. A000081, A000311, A000669, A001678, A005805, A141268, A292504, A300660, A316656.
%K A005804 nonn,easy
%O A005804 1,2
%A A005804 _N. J. A. Sloane_
%E A005804 More terms, comment from _Christian G. Bower_, Dec 15 1999