%I #74 Nov 10 2023 15:57:49
%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 Number of 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 Lim_{n->infinity} a(n)^(1/n) = (1+sqrt(5))/2, for more detailed asymptotics see Odlyzko 1982 reference. - _Vaclav Kotesovec_, Jul 29 2014
%C From _Jianing Song_, Nov 02 2019: (Start)
%C 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".
%C 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.
%C 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".
%C 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)
%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 Lucia Di Vizio, Gwladys Fernandes, and Marni Mishna, <a href="https://arxiv.org/abs/2309.07680">Inhomogeneous order 1 iterative functional equations with applications to combinatorics</a>, arXiv:2309.07680 [math.CO], 2023. See p. 3.
%H P. 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="https://web.archive.org/web/20110814045253/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 *)
%o (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
%Y Cf. A125295.
%K nonn
%O 0,6
%A _Eric W. Weisstein_