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
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.
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
KEYWORD
nonn
AUTHOR
STATUS
approved