A006677 - OEIS

%I M1806 #63 Dec 14 2019 21:41:42

%S 1,2,7,41,346,3797,51157,816356,15050581,314726117,7359554632,

%T 190283748371,5389914888541,165983936096162,5521346346543307,

%U 197294173392918461,7536892461493548226,306520422583290179057,13222422454704116605057,603006160203712090160876

%N Number of planted binary phylogenetic trees with n labels.

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

%D 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.

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

%D Simon Plouffe, Master's Thesis, uqam 1992.

%H N. J. A. Sloane, <a href="/A006677/b006677.txt">Table of n, a(n) for n = 1..101</a>

%H L. R. Foulds and R. W. Robinson, <a href="/A006677/a006677.pdf">Enumeration of binary phylogenetic trees</a>, pp. 187-202, Lecture Notes in Math., 884, Springer, Berlin-New York, 1981. (Annotated scanned copy)

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=160">Encyclopedia of Combinatorial Structures 160</a>

%H Simon Plouffe, <a href="http://arxiv.org/abs/0911.4975">Approximations of generating functions and a few conjectures</a>, arXiv:0911.4975 [math.NT], 2009, Master's Thesis.

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%F Stirling transform of A001147(n-1).

%F 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

%F E.g.f.: 1-(3-2*exp(x))^(1/2). - _Simon Plouffe_, Feb 17 2011

%F a(n) ~ sqrt(3) * n! / (2*sqrt(Pi) * n^(3/2) * (log(3/2))^(n-1/2)). - _Vaclav Kotesovec_, Feb 15 2015

%F 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

%F 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

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

%p 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

%t 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_ *)

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

%o (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 */

%K nonn,nice,easy

%O 1,2

%A _N. J. A. Sloane_, _Simon Plouffe_

%E More terms, formula and comment from _Christian G. Bower_, Dec 15 1999