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.

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

Author

Paul D. Hanna, May 11 2006

Keywords

• nonn

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

Examples

			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)
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..1000
• Eric Weisstein's World of Mathematics, B-Tree.

Crossrefs

Cf. A092684 (similar recurrence); B-trees: A014535 (order 3), A037026 (order 4), A058521 (order 5).

Cf. A011973.

Cf. A000081, A000311, A001678, A048816, A079500, A120803, A316624, A320154, A320160, A320169.

Programs

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 *)

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

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