A014535 Number of B-trees of order 3 with n leaves.

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

Offset: 0

Author

Eric W. Weisstein

Keywords

• nonn

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
• Lucia Di Vizio, Gwladys Fernandes, and Marni Mishna, Inhomogeneous order 1 iterative functional equations with applications to combinatorics, arXiv:2309.07680 [math.CO], 2023. See p. 3.
• 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

Crossrefs

Cf. A125295.

Programs

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

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

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.