|
|
A003214
|
|
Number of binary forests with n nodes.
(Formerly M0775)
|
|
5
|
|
|
1, 1, 2, 3, 6, 10, 20, 37, 76, 152, 320, 672, 1454, 3154, 6959, 15439, 34608, 77988, 176985, 403510, 924683, 2127335, 4913452, 11385955, 26468231, 61700232, 144206269, 337837221, 793213550, 1866181155, 4398867672, 10387045476, 24567374217, 58196129468, 138056734916
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
From Piet Hut, Nov 07 2003: "Number of ways to place n stars in stable hierarchical multiple star systems (where each stable multiple is a binary tree: around its center of mass two multiple star systems revolve, each of which can be a singleton or a nontrivial multiple star system).
"For example, a(1) = 1 : *; a(2) = 2 : (**), * *; a(3) = 3 : ((**)*), (**) *, * * *; a(4) = 6 : (((**)*)*), ((**)(**)), ((**)*) *, (**) (**), (**) * *, * * * * ."
|
|
REFERENCES
|
L. F. Meyers, Corrections and additions to Tree Representations in Linguistics. Report 3, 1966, p. 138. Project on Linguistic Analysis, Ohio State University Research Foundation, Columbus, Ohio.
L. F. Meyers and W. S.-Y. Wang, Tree Representations in Linguistics. Report 3, 1963, pp. 107-108. Project on Linguistic Analysis, Ohio State University Research Foundation, Columbus, Ohio.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: exp( Sum_{i>=1} G001190(x^i)/i ), where G001190 = g.f. for A001190.
a(n) ~ c * d^n / n^(3/2), where d = A086317 = 2.4832535361726368585622885181... and c = 0.9874010699028009804... . - Vaclav Kotesovec, Apr 19 2016
|
|
MAPLE
|
b:= proc(n) option remember; `if`(n<2, n, `if`(n::odd, 0,
(t-> t*(1-t)/2)(b(n/2)))+add(b(i)*b(n-i), i=1..n/2))
end:
a:= proc(n) option remember; `if`(n=0, 1, add(add(d*b(d),
d=numtheory[divisors](j))*a(n-j), j=1..n)/n)
end:
|
|
MATHEMATICA
|
terms = 35; (* G = G001190 *) G[_] = 0; Do[G[x_] = x + (1/2)*(G[x]^2 + G[x^2]) + O[x]^terms // Normal, terms]; A[x_] = Exp[Sum[G[x^i]/i, {i, 1, terms}]] + O[x]^terms; CoefficientList[A[x], x](* Jean-François Alcover, Nov 18 2011, updated Jan 12 2018 *)
(* b = A001190 *) b[n_] := b[n] = If[OddQ[n], Sum[b[k] b[n-k], {k, 1, (n-1)/2}], Sum[b[k] b[n-k], {k, 1, n/2 - 1}] + (1/2) b[n/2] (1+b[n/2])]; b[0] = 0; b[1] = 1;
etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[ Sum[d p[d], {d, Divisors[j]}] b[n-j], {j, 1, n}]/n]; b];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|