A037026 -id:A037026 - cp's OEIS frontend

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-2k) 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

Paul D. Hanna, May 11 2006

nonn

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

			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)

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

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.

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

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), ", "))

/* 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), ", "))

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

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

A058521 B-trees of order 5 with n labeled leaves.

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 7, 11, 20, 36, 67, 121, 215, 377, 657, 1154, 2045, 3666, 6628, 12063, 22079, 40642, 75264, 140191, 262457, 493297, 929703, 1754941, 3314509, 6258052, 11803995, 22232306, 41801393, 78453563, 146987053, 274957984

Offset: 1

N. J. A. Sloane, Dec 21 2000

nonn

Index entries for sequences related to rooted trees

Cf. A014535, A037026.

spec := [ B, {B=Union(Z, Subst(M, B)), M=Union(Prod(Z,Z),Prod(Z,Z,Z),Prod(Z$4),Prod(Z$5))} ]: [seq(combstruct[count](spec, size=n), n=1..40)];

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+x^3+x^4+x^5],{x,0,nn}],x];Table[a[n],{n,0,nn}]/.sol  (* Geoffrey Critzer, Mar 28 2013 *)

G.f. A(x) satisfies: A(x) = x + A(x^2+x^3+x^4+x^5). [Geoffrey Critzer, Mar 28 2013]

A106624 Expansion of g.f.: (1 - x^2 + x^3)/((1-x^2)(1-2x^2)).

Original entry on oeis.org

1, 0, 2, 1, 4, 3, 8, 7, 16, 15, 32, 31, 64, 63, 128, 127, 256, 255, 512, 511, 1024, 1023, 2048, 2047, 4096, 4095, 8192, 8191, 16384, 16383, 32768, 32767, 65536, 65535, 131072, 131071, 262144, 262143, 524288, 524287, 1048576, 1048575, 2097152

Offset: 0

Robert H Barbour, May 10 2005

Cumulative column frequency of occurrence of 0's and 1's iterated in a binary tree where each node in the tree holds a value of 0 or 1, beginning with a count of 1.

Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), (1979), Volume 11 Issue 2.
Huffman, D. A., A method for the construction of minimum redundancy codes, Proc. IRE 40 (1951), 1098-1101.
Knuth, D. E., Dynamic Huffman coding. J. Algorithms 6 (1985), 163-180.

Vincenzo Librandi, Table of n, a(n) for n = 0..5000
G. C. Barnes et al., Balanced sample Binary Trees, ACM SIGCSE Bulletin, Volume 37 Issue 1, 2005 pp. 166-170.
P. N. Fenwick, Cumulative Frequency, Software: Practice and Experience, 1994.
C. Witteveen, Balanced Binary Trees, Slides.
Index entries for linear recurrences with constant coefficients, signature (0,3,0,-2).

Cf. A016116, A014535, A037026, A058518 - A058521, A000079 (bisection), A000225 (bisection).

[2^Floor(n/2) + Floor((-1)^n - 1)/2: n in [0..50]]; // Vincenzo Librandi, Aug 17 2011

A106624 := proc(N)
    2^floor(n/2)+((-1)^n-1)/2 ;
end proc:
seq(A106624(n),n=0..20) ; # R. J. Mathar, Apr 14 2018

Table[2^Floor[n/2] +Floor[(-1)^n-1]/2, {n,0,50}] (* G. C. Greubel, Feb 19 2019 *)

vector(50,n, n--; 2^floor(n/2) +floor((-1)^n-1)/2) \\ G. C. Greubel, Feb 19 2019

[2^floor(n/2) +floor((-1)^n-1)/2 for n in (0..50)] # G. C. Greubel, Feb 19 2019

a(n) = 2^floor(n/2) + floor((-1)^n - 1)/2. - N. J. A. Sloane, May 15 2005

New definition from N. J. A. Sloane, May 15 2008

Edited by N. J. A. Sloane, Aug 29 2008 at the suggestion of R. J. Mathar

A001131 Number of red-black rooted trees with n-1 internal nodes.

Original entry on oeis.org

0, 1, 2, 2, 3, 8, 14, 20, 35, 64, 122, 260, 586, 1296, 2708, 5400, 10468, 19888, 37580, 71960, 140612, 279264, 560544, 1133760, 2310316, 4750368, 9876264, 20788880, 44282696, 95241664, 206150208, 447470464, 970862029, 2100029344

Offset: 0

Frank Ruskey

nonn

Are a(2) = a(3) = 2 and a(4) = 3 the only primes in this sequence? - Jonathan Vos Post, Jun 17 2005

F. Ruskey, Information on Red-Black Trees
Eric Weisstein's World of Mathematics, Red-Black Tree.
Index entries for sequences related to rooted trees

Cf. A001137, A014535, A037026.

spec := [B, {B=Union(Z, Subst(M, B)), M=Union(Prod(Z,Z),Prod(Z,Z,Z,Z))} ]; [seq(combstruct[count](spec, size=2*n), n=0..40)]; # N. J. A. Sloane, Dec 21 2000. Compare A014535, A037026.
a := proc(n) option remember; if n < 3 then return n fi; add(binomial(2*k, n-2*k)*a(k), k = iquo(n,4)..iquo(n,2)) end:
seq(a(n), n=0..33); # Peter Luschny, Oct 23 2019

m = 34; A[_] = 0;
Do[A[x_] = x + x^2 + A[(x + x^2)^2] + O[x]^m // Normal, {m}];
CoefficientList[A[x], x] (* Jean-François Alcover, Oct 23 2019 *)

{a(n)=local(A=x+x^2+x*O(x^n)); for(i=1, n, A=x+x^2+subst(A,x,(x+x^2)^2+x*O(x^n))); polcoeff(A, n)} \\ Paul D. Hanna, Jun 14 2012

a(1) = 1, a(2) = 2 and for n>2: a(n) = Sum_[n/4 <= m <= n/2] binomial(2m,n-2m)*a(m), John Moon, as quoted in Ruskey. - Jonathan Vos Post, Jun 17 2005.

G.f. satisfies: A(x) = x+x^2 + A((x+x^2)^2). - Paul D. Hanna, Jun 14 2012

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A058521 B-trees of order 5 with n labeled leaves.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A106624 Expansion of g.f.: (1 - x^2 + x^3)/((1-x^2)*(1-2*x^2)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A001131 Number of red-black rooted trees with n-1 internal nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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-2k) for n >= 2, with a(0)=0, a(1)=1.

A106624 Expansion of g.f.: (1 - x^2 + x^3)/((1-x^2)(1-2x^2)).