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

%I

%S 0,1,1,1,1,2,2,3,4,5,8,14,23,32,43,63,97,149,224,332,489,727,1116,

%T 1776,2897,4782,7895,12909,20752,32670,50426,76767,116206,176289,

%U 269615,416774,650647,1023035,1614864,2551783,4028217,6344749,9966479,15614300,24407844

%N B-trees of order 3 with n leaves.

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

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

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

%H Alois P. Heinz, <a href="/A014535/b014535.txt">Table of n, a(n) for n = 0..1000</a>

%H Ph. Flajolet and A. Odlyzko, <a href="http://algo.inria.fr/flajolet/Publications/FlOd90b.pdf">Singularity analysis of generating functions</a>, SIAM J. Discrete Math., vol 3 (1990) pp. 216-240. See p. 20.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 91

%H A. M. Odlyzko, <a href="https://doi.org/10.1016/0001-8708(82)90005-6">Periodic oscillations of coefficients of power series that satisfy functional equations</a>, Advances in Mathematics, Volume 44, Issue 2, May 1982, pp. 180-205.

%H F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/inf/tree/BTrees.html">Information on B-Trees</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/B-Tree.html">B-Tree.</a>

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

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

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

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

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

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

%K nonn

%O 0,6

%A _Eric W. Weisstein_

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 July 22 10:03 EDT 2019. Contains 325219 sequences. (Running on oeis4.)