login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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.

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

From Jianing Song, Nov 02 2019: (Start)

For n > 0, a(n) is also number of length-n sequences (d_1, d_2, ..., d_n) such that: (a) d_1 = 0, d_i > 0 for 2 <= i <= n; (b) for all 1 <= t <= n, at least one of d_i and d_(i+1) is equal to M = max_{t=1..n} d_t; (c) for all 1 <= i < j <= n+1, if max{d_i, d_j} < d_t for i < t < j, then between d_i and d_j there are exactly 1 or 2 terms equal to max{d_i, d_j} + 1. Here d_(n+1) = d_1. For example, for n = 8 there are four such sequences: (0, 3, 2, 3, 1, 3, 2, 3), (0, 2, 2, 1, 2, 2, 1, 2), (0, 2, 2, 1, 2, 1, 2, 2), (0, 2, 1, 2, 2, 1, 2, 2). For convention let's call such sequences "R sequences with largest term M".

Note that for M > 0, (0, d_2, d_3, ..., d_n1, 1, e_2, e_3, ..., e_n2) (d_t, e_u > 1) is an "R sequence with largest term M" if and only if (0, d_2-1, d_3-1, ..., d_n1-1) and (0, e_2-1, e_3-1, ..., e_n2-1) are both "R sequences with largest term M-1"; similarly, (0, d_2, d_3, ..., d_n1, 1, e_2, e_3, ..., e_n2, 1, f_2, f_3, ..., f_n3) (d_t, e_u, f_v > 1) is an "R sequence with largest term M" if and only if (0, d_2-1, d_3-1, ..., d_n1-1), (0, e_2-1, e_3-1, ..., e_n2-1) and (0, f_2-1, f_3-1, ..., f_n3-1) are all "R sequences with largest term M-1". From this we can see that each "R sequence with largest term M" of length-n is isomorphic to a B-tree of order 3 with M levels and n leaves, where the root is counted as the 0th level.

The condition (c) above is equivalent to: (c') there are no three or more consecutive M's in the sequence; if we eliminate all the M's, we get a shorter "R sequence with largest term M-1".

The number of B-trees of order 3 with M levels or the number of "R sequences with largest term M" is given by A125295(M). (End)

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

P. 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 *)

PROG

(PARI) a(n) = if(n, my(v=vector(n)); v[1]=1; for(i=2, n, v[i]=sum(k=ceil(i/3), i\2, binomial(k, 3*k - i)*v[k])); v[n], 0) \\ Jianing Song, Nov 02 2019

CROSSREFS

Cf. A125295.

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 July 16 13:33 EDT 2020. Contains 335788 sequences. (Running on oeis4.)