cp's OEIS Frontend

A007151 Number of planted evolutionary trees of magnitude n.

%I A007151 M3064 #44 Dec 29 2024 14:35:22
%S A007151 1,3,19,198,2906,55018,1275030,34947664,1105740320,39661089864,
%T A007151 1590232358584,70482038536880,3421732373367504,180574681050278960,
%U A007151 10292371442183694832,630125771602386523392,41239934114630205030656
%N A007151 Number of planted evolutionary trees of magnitude n.
%C A007151 Also number of labeled rooted trees with n generators. (A generator is a leaf or a node with just one child.) - _Christian G. Bower_, Jun 07 2005
%D A007151 L. R. Foulds and R. W. Robinson, Counting certain classes of evolutionary trees with singleton labels, Congress. Num., 44 (1984), 65-88.
%D A007151 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007151 G. C. Greubel, <a href="/A007151/b007151.txt">Table of n, a(n) for n = 1..360</a>
%H A007151 L. R. Foulds and R. W. Robinson, <a href="/A007151/a007151.pdf">Counting certain classes of evolutionary trees with singleton labels</a>, Congress. Num., 44 (1984), 65-88. (Annotated scanned copy)
%H A007151 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A007151 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A007151 E.g.f. satisfies (2-x)*A(x) = x - 1 + exp(A(x)). - _Christian G. Bower_, Jun 07 2005
%F A007151 a(n) = Sum_{k=1..(n-1)} (n+k-1)!*Sum_{j=1..k} (1/(k-j)!)*Sum_{i=0..(n-1)} binomial(j+i-1,j-1)*Sum_{m=0..j} 2^m*(-1)^(m+i)*Stirling2(n-m+j-i-1,j-m)/(m!*(n-m+j-i-1)!), n>1, a(1)=1. - _Vladimir Kruchinin_, Aug 07 2012
%F A007151 a(n) ~ sqrt(LambertW(1)+1) * n^(n-1) * (LambertW(1))^n / (exp(n) * (2*LambertW(1)-1)^(n-1/2)). - _Vaclav Kotesovec_, Jan 08 2014
%p A007151 A007151 := proc(n)
%p A007151     local k,j,i,m ,a;
%p A007151     if n =1 then
%p A007151         1;
%p A007151     else
%p A007151         a := 0 ;
%p A007151         for k from 1 to n-1 do
%p A007151         for j from 1 to k do
%p A007151         for i from 0 to n-1 do
%p A007151         for m from 0 to j do
%p A007151              a := a+(n+k-1)! /(k-j)! *binomial(j+i-1,j-1) *2^m *(-1)^(m+i) *combinat[stirling2](n-m+j-i-1,j-m) / m! /(n-m+j-i-1)! ;
%p A007151         end do:
%p A007151         end do:
%p A007151         end do:
%p A007151         end do:
%p A007151         a ;
%p A007151     end if;
%p A007151 end proc:
%p A007151 seq(A007151(n),n=1..10) ; # _R. J. Mathar_, Mar 19 2018
%t A007151 Rest[CoefficientList[InverseSeries[Series[(1 - E^x + 2*x)/(1 + x),{x,0,20}],x],x] * Range[0,20]!] (* _Vaclav Kotesovec_, Jan 08 2014 *)
%o A007151 (Maxima) a(n):=if n=1 then 1 else (sum((n+k-1)!*sum(1/((k-j)!)*sum(binomial(j+i-1,j-1)*sum((2^m*(-1)^(m+i)*stirling2(n-m+j-i-1,j-m))/(m!*(n-m+j-i-1)!),m,0,j),i,0,n-1),j,1,k),k,1,n-1)); /* _Vladimir Kruchinin_, Aug 07 2012 */
%o A007151 (PARI) for(n=1,20, print1(if(n==1,1,sum(k=1,n-1, (n+k-1)!*sum(j=1,k, (1/(k-j)!)* sum(i=0,n-1, binomial(j+i-1,j-1)*sum(m=0,j, 2^m*(-1)^(m+i)* stirling(n-m+j-i-1,j-m,2)/(m!*(n-m+j-i-1)!)))))), ", ")) \\ _G. C. Greubel_, Nov 26 2017
%Y A007151 Cf. A007152, A108521, A108522, A000169, A000311.
%K A007151 nonn,easy
%O A007151 1,2
%A A007151 _Robert W. Robinson_