login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006677 Number of planted binary phylogenetic trees with n labels.
(Formerly M1806)
12
1, 2, 7, 41, 346, 3797, 51157, 816356, 15050581, 314726117, 7359554632, 190283748371, 5389914888541, 165983936096162, 5521346346543307, 197294173392918461, 7536892461493548226, 306520422583290179057, 13222422454704116605057, 603006160203712090160876 (list; graph; refs; listen; history; text; internal format)
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
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)
Simon Plouffe, Approximations of generating functions and a few conjectures, arXiv:0911.4975 [math.NT], 2009, Master's Thesis.
N. J. A. Sloane, Transforms
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: A107376 A220896 A087804 * A346271 A101390 A113144
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
More terms, formula and comment from Christian G. Bower, Dec 15 1999
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 06:15 EDT 2024. Contains 371265 sequences. (Running on oeis4.)