login
This site is supported by donations 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)
6
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

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 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: A107376 A220896 A087804 * A101390 A113144 A320415

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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 02:18 EDT 2019. Contains 328244 sequences. (Running on oeis4.)