A005373 A class of rooted trees with n nodes. (Formerly M3083)

1, 3, 21, 231, 3495, 67455, 1584765, 43897455, 1400923755, 50619052575, 2042745514425, 91066568444775, 4444738893770175, 235731740255186175, 13499365993279291125, 830161812269496081375, 54564569247212367217875, 3817309552613869238301375

Offset

1,2

Comments

See Table 3 on page 32 of the Felsenstein reference: "The numbers of rooted trees with n labelled species, allowing some interior nodes to be labelled, but allowing no more than two immediate descendants of each interior node." - Joerg Arndt, Jun 02 2016

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=1..18.

J. Felsenstein, The number of evolutionary trees, Systematic Zoology, 27 (1978), 27-33.

J. Felsenstein, The number of evolutionary trees, Systematic Zoology, 27 (1978), 27-33. (Annotated scanned copy)

Index entries for sequences related to rooted trees

Formula

a(n) = Sum_{m=1..n} Sum_{p=1..n-m} V(n,m,p) where V(1,0,0)=1, V(1,i,j)=0, and V(n,m,p) = [p>0]*((2*n-2*m-p-2)*V(n-1,m,p1) + (n-m-p)*V(n-1,m,p-1)) + [m>0]*((n-2*m-p)*V(n-1,m-1,p) + (p+1)*V(n-1,m-1,p+1)) + [2*n-2*m-p-3>0]*(2*n-2*m-p-3)*V(n-1,m,p) with [t>0]=1 if t>0 and 0 otherwise. - Sean A. Irvine, Jun 02 2016

Crossrefs

Sequence in context: A119097 A326604 A008545 * A078586 A179331 A138903

Adjacent sequences: A005370 A005371 A005372 * A005374 A005375 A005376

Keyword

nonn

Author

N. J. A. Sloane.

Extensions

More terms from Sean A. Irvine, Jun 02 2016

Status

approved