A007151 Number of planted evolutionary trees of magnitude n. (Formerly M3064)

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

Offset

1,2

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

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

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

Prog

(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

Crossrefs

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

Sequence in context: A001832 A195511 A123681 * A269787 A303927 A288693

Adjacent sequences: A007148 A007149 A007150 * A007152 A007153 A007154

Keyword

nonn,easy

Author

Robert W. Robinson

Status

approved