A006677 Number of planted binary phylogenetic trees with n labels. (Formerly M1806)

1, 2, 7, 41, 346, 3797, 51157, 816356, 15050581, 314726117, 7359554632, 190283748371, 5389914888541, 165983936096162, 5521346346543307, 197294173392918461, 7536892461493548226, 306520422583290179057, 13222422454704116605057, 603006160203712090160876

Offset

1,2

Comments

Series-reduced planted binary trees where each leaf is a nonempty subset of the set of n labels.

References

Foulds, L. R.; Robinson, R. W. 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.

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

Simon Plouffe, Master's Thesis, uqam 1992.

Links

N. J. A. Sloane, Table of n, a(n) for n = 1..101

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)

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 160

Simon Plouffe, Approximations of generating functions and a few conjectures, arXiv:0911.4975 [math.NT], 2009, Master's Thesis.

N. J. A. Sloane, Transforms

Index entries for sequences related to rooted trees

Formula

Stirling transform of A001147(n-1).

E.g.f.: exp(x)/(3 - 2*exp(x))^(1/2). This sequence is the Stirling transform of the sequence ( (2n-1)!! + n(2n-3)!! )_(n >= 0) = (1, 2, 5, 24, 165, 1470, 16065, 207900, ...) with e.g.f. (1+x)/(1-2*x)^(1/2). (Both remarks assume offset 0.) - David Callan, Jul 22 2008

E.g.f.: 1-(3-2*exp(x))^(1/2). - Simon Plouffe, Feb 17 2011

a(n) ~ sqrt(3) * n! / (2*sqrt(Pi) * n^(3/2) * (log(3/2))^(n-1/2)). - Vaclav Kotesovec, Feb 15 2015

Recurrence: a(1) = 1, a(n) = 1 + Sum_{0<k<n} binomial(n-1,k)*a(k)*a(n-k). - Vladimir Reshetnikov, Nov 14 2016

E.g.f. A(x) = y satisfies 0 = 1 - exp(x) + y - y^2/2 and (1 - y)*y' = exp(x). - Michael Somos, Nov 16 2016

Example

G.f. = x + 2*x^2 + 7*x^3 + 41*x^4 + 346*x^5 + 3797*x^6 + 51157*x^7 + 816356*x^8 + ...

Maple

stirtr:= proc(p) proc(n) add(p(k) *combinat[stirling2](n, k), k=0..n) end end: f:= n-> `if`(n=0, 1, (2*n-2)!/ (n-1)!/ 2^(n-1)): a:= stirtr(f): seq(a(n), n=1..20); # Alois P. Heinz, Sep 15 2008

Mathematica

max = 18; f[x_] := 1 - (3 - 2*Exp[x])^(1/2); Drop[ CoefficientList[ Series[ f[x], {x, 0, max}], x]*Range[0, max]!, 1] (* Jean-François Alcover, Dec 20 2011, after Simon Plouffe *)
a[1] = 1; a[n_] := a[n] = 1 + Sum[Binomial[n-1, k] a[k] a[n-k], {k, 1, n-1}]; Table[a[n], {n, 1, 20}] (* Vladimir Reshetnikov, Nov 14 2016 *)

Prog

(PARI) {a(n) = if( n<0, 0, n! * polcoeff( 1 - sqrt(3 - 2*exp(x + x*O(x^n))), n))}; /* Michael Somos, Nov 16 2016 */

Crossrefs

Sequence in context: A220896 A087804 A378325 * A346271 A101390 A113144

Adjacent sequences: A006674 A006675 A006676 * A006678 A006679 A006680

Keyword

nonn,nice,easy

Author

N. J. A. Sloane, Simon Plouffe

Extensions

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

Status

approved