|
Search: id:A119262
|
|
|
| A119262 |
|
Number of B-trees of order infinity with n leaves, where a(n) = Sum_{k=1..[n/2]} a(k)*C(n-k-1,n-2*k) for n>=2, with a(0)=0, a(1)=1. |
|
+0
4
|
|
| 0, 1, 1, 1, 2, 3, 5, 8, 14, 25, 46, 85, 158, 294, 548, 1022, 1908, 3567, 6683, 12556, 23669, 44781, 85046, 162122, 310157, 595322, 1146057, 2212004, 4278908, 8292738, 16097018, 31286456, 60873574, 118543329, 231009934, 450434739, 878687665
(list; graph; listen)
|
|
|
OFFSET
|
0,5
|
|
|
COMMENT
|
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 the root has 0 or at least m/2 children, all end-nodes are at the same level. This sequence is the limit of the B-trees as m --> infinity.
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
|
|
FORMULA
|
G.f. satisfies: A(x) = x + A(x^2/(1-x)). G.f. series: A(x) = Sum_{n>=0} x^(2^n)/D(n,x) where D(0,x)=1, D(n+1,x) = D(n,x)*[D(n,x) - x^(2^n)].
|
|
EXAMPLE
|
A(x) = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 5*x^6 + 8*x^7 + 14*x^8 +...
Series form:
A(x) = x + x^2/(1-x) + x^4/((1-x)*((1-x)-x^2)) +
x^8/((1-x)*((1-x)-x^2)*((1-x)*((1-x)-x^2)-x^4)) +...
+ x^(2^n)/D(n,x) + x^(2^(n+1))/[D(n,x)*(D(n,x)-x^(2^n))] +...
|
|
PROGRAM
|
(PARI) {a(n)=if(n==0, 0, if(n==1, 1, sum(k=1, n\2, a(k)*binomial(n-k-1, n-2*k))))}
|
|
CROSSREFS
|
Cf. A092684 (similar recurrence); B-trees: A014535 (order 3), A037026 (order 4), A058521 (order 5).
Sequence in context: A128021 A036241 A125028 this_sequence A062178 A065955 A104880
Adjacent sequences: A119259 A119260 A119261 this_sequence A119263 A119264 A119265
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Paul D. Hanna (pauldhanna(AT)juno.com), May 11 2006
|
|
|
Search completed in 0.002 seconds
|
