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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A014535 B-trees of order 3 with n leaves. 11
0, 1, 1, 1, 1, 2, 2, 3, 4, 5, 8, 14, 23, 32, 43, 63, 97, 149, 224, 332, 489, 727, 1116, 1776, 2897, 4782, 7895, 12909, 20752, 32670, 50426, 76767, 116206, 176289, 269615, 416774, 650647, 1023035, 1614864, 2551783, 4028217, 6344749, 9966479, 15614300, 24407844 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

A B-tree of order m is an ordered tree such that every node has at most m children, the root has at least 2 children, every node except for the root has 0 or at least m/2 children, all end-nodes are at the same level.

Limit n->infinity a(n)^(1/n) = (1+sqrt(5))/2, for more detailed asymptotics see Odlyzko 1982 reference. - Vaclav Kotesovec, Jul 29 2014

REFERENCES

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.6 Otter's tree enumeration constants, p. 311.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Ph. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math., vol 3 (1990) pp. 216-240. See p. 20.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 91

A. M. Odlyzko, Periodic oscillations of coefficients of power series that satisfy functional equations, Advances in Mathematics, Volume 44, Issue 2, May 1982, pp. 180-205.

F. Ruskey, Information on B-Trees

Eric Weisstein's World of Mathematics, B-Tree.

Index entries for sequences related to rooted trees

FORMULA

G.f. satisfies A(x) = x + A(x^2+x^3).

a(0) = 0, a(1) = 1, a(n) = sum_{k=ceiling(n/3)..floor(n/2)} binomial(k, 3*k - n)*a(k) - Jean-François Alcover, Jul 29 2014, after Steven Finch.

MAPLE

spec := [ B, {B=Union(Z, Subst(M, B)), M=Union(Prod(Z, Z), Prod(Z, Z, Z))} ]: seq(combstruct[count](spec, size=n), n=0..36); # Paul Zimmermann

MATHEMATICA

terms = 45; A[_] = 0; Do[A[x_] = x + A[x^2 + x^3] + O[x]^terms // Normal, terms]; CoefficientList[A[x], x] (* Jean-François Alcover, Oct 23 2012, from g.f., updated Jan 10 2018 *)

a[0] = 0; a[1] = 1; a[n_] := a[n] = Sum[Binomial[k, 3*k - n]*a[k], {k, Ceiling[n/3], Floor[n/2]}]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jul 29 2014 *)

CROSSREFS

Sequence in context: A100483 A182613 A184259 * A210642 A263140 A205006

Adjacent sequences:  A014532 A014533 A014534 * A014536 A014537 A014538

KEYWORD

nonn

AUTHOR

Eric W. Weisstein

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 June 25 10:10 EDT 2019. Contains 324351 sequences. (Running on oeis4.)