|
| |
|
|
A014535
|
|
Number of 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
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
|
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
|
| |
|
|
