A005640 Number of phylogenetic trees with n labels.

1, 1, 2, 8, 64, 832, 15104, 352256, 10037248, 337936384, 13126565888, 577818263552, 28425821618176, 1545553369366528, 92034646352592896, 5956917762776367104, 416397789920380321792, 31262503202358260924416, 2508985620606225641111552, 214348807882902869374926848, 19422044917978876510600167424

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

Each node of the tree is a subset of the labeled set {1,...,n}. If the subset node is empty, it must have degree at least 3.

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.26.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..100
• L. R. Foulds and R. W. Robinson, Determining the asymptotic number of phylogenetic trees, pp. 110-126 of Combinatorial Mathematics VII (Newcastle, August 1979), ed. R. W. Robinson, G. W. Southern and W. D. Wallis. Lecture Notes in Math., 829 (1980), 110-126. (Annotated scanned copy)
• J. P. Hayes, Enumeration of fanout-free Boolean functions, J. ACM, 23 (1976), 700-709.
• K. L. Kodandapani and S. C. Seth, On combinational networks with restricted fan-out, IEEE Trans. Computers, 27 (1978), 309-318. (Annotated scanned copy)
• N. J. A. Sloane, Transforms
• Index entries for sequences related to trees

Crossrefs

Cf. A000311, A005172, A005263, A006351.

Programs

Mathematica

a[n_ /; n > 2] := 2^(n-1)*(n-2)!*Sum[ Binomial[n+k-2, n-2]*Sum[ (-1)^j*Binomial[k, j]*Sum[ ((-1)^l*2^(j-l)*Binomial[j, l]*(j-l)!*StirlingS1[n+j-l-2, j-l])/(n+j-l-2)!, {l, 0, j}], {j, 1, k}], {k, 1, n-2}]; a[0] = a[1] = 1; a[2] = 2; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Apr 10 2012, after Vladimir Kruchinin *)

Formula

STIRLING transform of A005263.

E.g.f.: 1+B(x)-B(x)^2 where B(x) is e.g.f. of A005172.

For n >= 2, a(n) = 2^n*A006351(n) = 2^(n+1)*A000311(n).

Extensions

More terms, formula and comment from Christian G. Bower, Nov 15 1999