|
|
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
|
|
|
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
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
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|