A007151 Number of planted evolutionary trees of magnitude n.

1, 3, 19, 198, 2906, 55018, 1275030, 34947664, 1105740320, 39661089864, 1590232358584, 70482038536880, 3421732373367504, 180574681050278960, 10292371442183694832, 630125771602386523392, 41239934114630205030656

Offset: 1

Author

Robert W. Robinson

Keywords

• nonn
• easy

Comments

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

References

• L. R. Foulds and R. W. Robinson, Counting certain classes of evolutionary trees with singleton labels, Congress. Num., 44 (1984), 65-88.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• G. C. Greubel, Table of n, a(n) for n = 1..360
• L. R. Foulds and R. W. Robinson, Counting certain classes of evolutionary trees with singleton labels, Congress. Num., 44 (1984), 65-88. (Annotated scanned copy)
• Index entries for sequences related to rooted trees
• Index entries for sequences related to trees

Crossrefs

Cf. A007152, A108521, A108522, A000169, A000311.

Programs

Maple

A007151 := proc(n)
    local k,j,i,m ,a;
    if n =1 then
        1;
    else
        a := 0 ;
        for k from 1 to n-1 do
        for j from 1 to k do
        for i from 0 to n-1 do
        for m from 0 to j do
             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)! ;
        end do:
        end do:
        end do:
        end do:
        a ;
    end if;
end proc:
seq(A007151(n),n=1..10) ; # R. J. Mathar, Mar 19 2018

Mathematica

Rest[CoefficientList[InverseSeries[Series[(1 - E^x + 2*x)/(1 + x),{x,0,20}],x],x] * Range[0,20]!] (* Vaclav Kotesovec, Jan 08 2014 *)

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 */

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

Formula

E.g.f. satisfies (2-x)*A(x) = x - 1 + exp(A(x)). - Christian G. Bower, Jun 07 2005

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

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