login
A119262
Number of B-trees of order infinity with n leaves, where a(n) = Sum_{k=1..floor(n/2)} a(k)*C(n-k-1,n-2*k) for n >= 2, with a(0)=0, a(1)=1.
17
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
OFFSET
0,5
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 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.
Starting with offset 2, the eigensequence of triangle A011973. - Gary W. Adamson, Jul 08 2012
Number of balanced series-reduced rooted plane trees with n leaves. A rooted tree is series-reduced if every non-leaf node has at least two branches, and balanced if all leaves are the same distance from the root. - Gus Wiseman, Oct 07 2018
LINKS
Eric Weisstein's World of Mathematics, B-Tree.
FORMULA
G.f. A(x) satisfies: A(x) = x + A(x^2/(1-x)).
G.f.: 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)].
G.f.: x = Sum_{n>=1} a(n) * x^n * (1-x^n) / (1+x)^(n-1). - Paul D. Hanna, Jul 31 2013
Conjecture: Let M_n be an n X n matrix whose elements are m_ij = 0 for i < j - 1, m_ij = -1 for i = j - 1, and m_ij = binomial(i - j, n - i) otherwise. Then a(n + 1) = Det(M_n). - Benedict W. J. Irwin, Apr 19 2017
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))] + ...
Terms also satisfy the series:
x = x*(1-x) + x^2*(1-x^2)/(1+x) + x^3*(1-x^3)/(1+x)^2 + 2*x^4*(1-x^4)/(1+x)^3 + 3*x^5*(1-x^5)/(1+x)^4 + 5*x^6*(1-x^6)/(1+x)^5 + 8*x^7*(1-x^7)/(1+x)^6 + 14*x^8*(1-x^8)/(1+x)^7 + 25*x^9*(1-x^9)/(1+x)^8 + ... + a(n)*x^n*(1-x^n)/(1+x)^(n-1) + ...
From Gus Wiseman, Oct 07 2018: (Start)
The a(1) = 1 through a(7) = 8 balanced series-reduced rooted plane trees:
o (oo) (ooo) (oooo) (ooooo) (oooooo) (ooooooo)
((oo)(oo)) ((oo)(ooo)) ((oo)(oooo)) ((oo)(ooooo))
((ooo)(oo)) ((ooo)(ooo)) ((ooo)(oooo))
((oooo)(oo)) ((oooo)(ooo))
((oo)(oo)(oo)) ((ooooo)(oo))
((oo)(oo)(ooo))
((oo)(ooo)(oo))
((ooo)(oo)(oo))
(End)
MATHEMATICA
nn=38; f[x_]:=Sum[a[n]x^n, {n, 0, nn}]; a[0]=0; sol=SolveAlways[0==Series[f[x]-x-f[x^2/(1-x)], {x, 0, nn}], x]; Table[a[n], {n, 0, nn}]/.sol (* Geoffrey Critzer, Mar 28 2013 *)
PROG
(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))))
for(n=1, 20, print1(a(n), ", "))
(PARI) /* From: A(x) = x + A(x^2/(1-x)) */
{a(n)=local(A=x); for(i=1, n, A=x+subst(A, x, x^2/(1-x+x*O(x^n)))); polcoeff(A, n)}
for(n=1, 20, print1(a(n), ", "))
(PARI) /* From: x = Sum_{n>=1} a(n)*x^n*(1-x^n)/(1+x)^(n-1) */
a(n)=if(n==1, 1, -polcoeff(sum(k=1, n-1, a(k)*x^k*(1-x^k)/(1+x+x*O(x^n))^(k-1)), n))
for(n=1, 20, print1(a(n), ", ")) \\ Paul D. Hanna, Jul 31 2013
CROSSREFS
Cf. A092684 (similar recurrence); B-trees: A014535 (order 3), A037026 (order 4), A058521 (order 5).
Cf. A011973.
Sequence in context: A192633 A125028 A349777 * A177510 A062178 A173282
KEYWORD
nonn
AUTHOR
Paul D. Hanna, May 11 2006
STATUS
approved