A006677 Number of planted binary phylogenetic trees with n labels.

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

Offset: 1

Author

N. J. A. Sloane, Simon Plouffe

Keywords

• nonn
• nice
• easy

Comments

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

Examples

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

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

Programs

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

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

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_{0Vladimir 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

Extensions

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