login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003214 Number of binary forests with n nodes.
(Formerly M0775)
6
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

Alois P. Heinz, Table of n, a(n) for n = 0..2544 (first 201 terms from T. D. Noe)

Piet Hut, Home Page

FORMULA

Euler transform of A001190. - Michael Somos, Nov 10 2003

G.f.: exp( sum G001190(x^i)/i, i=1..infinity ), 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:

seq(a(n), n=0..40);  # Alois P. Heinz, Sep 11 2017

MATHEMATICA

max = 34; c[0] = 0; g[x_] = Sum[c[k]*x^k, {k, 0, max}]; eq[0] = Rest[ Thread[ CoefficientList[ (-2*x + 2*g[x] - g[x]^2 - g[x^2])/2, x] == 0]]; s[1] = First[ Solve[ First[eq[0]], c[1]]]; Do[ eq[k-1] = Rest[ eq[k-2]] /. s[k-1]; s[k] = First[ Solve[ First[eq[k-1]], c[k]]], {k, 2, max}]; sol = Flatten[ Table[ s[k], {k, 1*max}], 1]; f[x_] = Exp[ Sum[ g[x^i]/i, {i, 1, max}]] /. sol; CoefficientList[ Series[ f[x], {x, 0, max}], x](* Jean-François Alcover, Nov 18 2011 *)

(* 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];

a[n_] := etr[b][n]; Table[a[n], {n, 0, 34}] (* Jean-François Alcover, Mar 14 2016 *)

CROSSREFS

Cf. A001190.

Sequence in context: A045690 A007148 A093371 * A123423 A005195 A228835

Adjacent sequences:  A003211 A003212 A003213 * A003215 A003216 A003217

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 25 12:56 EDT 2017. Contains 292469 sequences.