A006679 Number of planted binary phylogenetic trees with n labels.

0, 1, 2, 10, 83, 946, 13772, 244315, 5113208, 123342166, 3369568817, 102831001120, 3467225430308, 128006254663561, 5135734326127862, 222498607683528550, 10352141336173618883, 514815201125079097006, 27251316075035460318032, 1529842445683171428183355

Offset: 0

Author

N. J. A. Sloane, Simon Plouffe

Keywords

• nonn

References

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

Links

• Gheorghe Coserea, Table of n, a(n) for n = 0..200
• L. R. Foulds, R. W. Robinson, Enumeration of binary phylogenetic trees Combinatorial mathematics, VIII (Geelong, 1980), pp. 187-202, Lecture Notes in Math., 884, Springer, Berlin-New York, 1981. Math. Rev. 83a:05071.
• L. R. Foulds and R. W. Robinson, Enumeration of binary phylogenetic trees, pp. 187-202, Lecture Notes in Math., 884, Springer, Berlin-New York, 1981. (Annotated scanned copy)
• Index entries for sequences related to rooted trees
• Index entries for sequences related to trees

Programs

Mathematica

CoefficientList[Series[(1 - Sqrt[1 + 2*E^x - 2*E^(2*x)])/E^x, {x, 0, 20}], x] * Range[0, 20]! (* Vaclav Kotesovec, Nov 29 2015 *)

Maxima

a(n):=sum(((sum((2^(1-k)*(2*k-2)!/(k-1)!*sum((stirling2(i,k)*k^(j-i))*binomial(j,i),i,0,j)),k,1,j))*(-1)^(n-j))*binomial(n,j),j,0,n); /* Vladimir Kruchinin, Nov 17 2015 */

PARI

x='x+O('x^33); Vec(serlaplace((1 - (1 + 2*exp(x) - 2*exp(x)^2)^(1/2))/exp(x))) \\ Gheorghe Coserea, Aug 04 2015

Formula

E.g.f: (1 - (1 + 2*exp(x) - 2*exp(x)^2)^(1/2))/exp(x). - Gheorghe Coserea, Aug 04 2015

a(n) = Sum_{j=0..n} C(n,j)*(-1)^(n-j)* Sum_{k=1..j} 2^(1-k)*(2*k-2)!/ (k-1)!* Sum_{i=0..j} stirling2(i,k)*k^(j-i)*C(j,i). - Vladimir Kruchinin, Nov 17 2015

a(n) ~ sqrt(3-sqrt(3)) * n^(n-1) / (log((1+sqrt(3))/2)^(n-1/2) * exp(n)). - Vaclav Kotesovec, Nov 29 2015

Extensions

More terms from Gheorghe Coserea, Aug 04 2015