

A014535


Btrees 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 Btree 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 endnodes 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 lengthn 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_21, d_31, ..., d_n11) and (0, e_21, e_31, ..., e_n21) are both "R sequences with largest term M1"; 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_21, d_31, ..., d_n11), (0, e_21, e_31, ..., e_n21) and (0, f_21, f_31, ..., f_n31) are all "R sequences with largest term M1". From this we can see that each "R sequence with largest term M" of lengthn is isomorphic to a Btree 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 M1".
The number of Btrees 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. 216240. 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. 180205.
F. Ruskey, Information on BTrees
Eric Weisstein's World of Mathematics, BTree.
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)  JeanFranç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] (* JeanFranç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}] (* JeanFranç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



