A092684 -id:A092684 - 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

A092683 Triangle, read by rows, such that the convolution of each row with {1,1} produces a triangle which, when flattened, equals this flattened form of the original triangle.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 3, 3, 2, 3, 6, 5, 5, 3, 6, 11, 10, 8, 9, 6, 11, 21, 18, 17, 15, 17, 11, 21, 39, 35, 32, 32, 28, 32, 21, 39, 74, 67, 64, 60, 60, 53, 60, 39, 74, 141, 131, 124, 120, 113, 113, 99, 113, 74, 141, 272, 255, 244, 233, 226, 212, 212, 187, 215, 141, 272, 527, 499

Offset: 0

Paul D. Hanna, Mar 04 2004

First column and main diagonal forms A092684. Row sums form A092685.

This triangle is the cascadence of binomial (1+x). More generally, the cascadence of polynomial F(x) of degree d, F(0)=1, is a triangle with d*n+1 terms in row n where the g.f. of the triangle, A(x,y), is given by: A(x,y) = ( x*H(x) - y*H(x*y^d) )/( x*F(y) - y ), where H(x) satisfies: H(x) = G*H(x*G^d)/x and G=G(x) satisfies: G(x) = x*F(G(x)) so that G = series_reversion(x/F(x)); also, H(x) is the g.f. of column 0. - Paul D. Hanna, Jul 17 2006

			Rows begin:
1;
1, 1;
2, 1, 2;
3, 3, 2, 3;
6, 5, 5, 3, 6;
11, 10, 8, 9, 6, 11;
21, 18, 17, 15, 17, 11, 21;
39, 35, 32, 32, 28, 32, 21, 39;
74, 67, 64, 60, 60, 53, 60, 39, 74;
141, 131, 124, 120, 113, 113, 99, 113, 74, 141;
272, 255, 244, 233, 226, 212, 212, 187, 215, 141, 272;
527, 499, 477, 459, 438, 424, 399, 402, 356, 413, 272, 527;
1026, 976, 936, 897, 862, 823, 801, 758, 769, 685, 799, 527, 1026; ...
The convolution of each row with {1,1} gives the triangle:
1, 1;
1, 2, 1;
2, 3, 3, 2;
3, 6, 5, 5, 3;
6, 11, 10, 8, 9, 6;
11, 21, 18, 17, 15, 17, 11;
21, 39, 35, 32, 32, 28, 32, 21;
39, 74, 67, 64, 60, 60, 53, 60, 39; ...
which, when flattened, equals the original triangle in flattened form.

Paul D. Hanna, Table of n, a(n) for n = 0..1325; rows 0..50 in flattened form.

Cf. A092684, A092685, A092686, A092689, A120894, A120898.

T(n,k)=if(n<0 || k>n,0, if(n==0 && k==0,1, if(n==1 && k<=1,1, if(k==n,T(n,0), T(n-1,k)+T(n-1,k+1)))))
for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print(""))

/* Generate Triangle by G.F. where F=1+x: */
{T(n,k)=local(A,F=1+x,d=1,G=x,H=1+x,S=ceil(log(n+1)/log(d+1))); for(i=0,n,G=x*subst(F,x,G+x*O(x^n)));for(i=0,S,H=subst(H,x,x*G^d+x*O(x^n))*G/x); A=(x*H-y*subst(H,x,x*y^d +x*O(x^n)))/(x*subst(F,x,y)-y); polcoeff(polcoeff(A,n,x),k,y)}
for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print()) \\ Paul D. Hanna, Jul 17 2006

T(n, k) = T(n-1, k) + T(n-1, k+1) for 0<=k

G.f.: A(x,y) = ( x*H(x) - y*H(x*y) )/( x*(1+y) - y ), where H(x) satisfies: H(x) = H(x^2/(1-x))/(1-x) and H(x) is the g.f. of column 0 (A092684). - Paul D. Hanna, Jul 17 2006

A120899 G.f. satisfies: A(x) = C(x)^2 * A(x^3*C(x)^4), where C(x) is the g.f. of the Catalan numbers (A000108).

Original entry on oeis.org

1, 2, 5, 16, 54, 186, 654, 2338, 8463, 30938, 114022, 423096, 1579049, 5922512, 22309350, 84354388, 320020227, 1217689680, 4645693038, 17766596202, 68092473570, 261486788434, 1005962436536, 3876412305114, 14960183283203

Offset: 0

Paul D. Hanna, Jul 14 2006

nonn

Column 0 of triangle A120898 (cascadence of 1+2x+x^2). Self-convolution of A120900.

			A(x) = 1 + 2*x + 5*x^2 + 16*x^3 + 54*x^4 + 186*x^5 + 654*x^6 +...
= C(x)^2 * A(x^3*C(x)^4) where
C(x) = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 132*x^6 +...
is the g.f. of the Catalan numbers (A000108): C(x) = 1 + x*C(x)^2.

Cf. A120898, A120900 (square-root), A120901, A120902; A000108; variants: A092684, A092687, A120895.

{a(n)=local(A=1+x,C=(1/x*serreverse(x/(1+2*x+x^2+x*O(x^n))))^(1/2)); for(i=0,n,A=C^2*subst(A,x,x^3*C^4 +x*O(x^n)));polcoeff(A,n,x)}

A120895 G.f. satisfies: A(x) = G(x)A(x^3G(x)^2) where G(x) is the g.f. of the Motzkin numbers (A001006).

Original entry on oeis.org

1, 1, 2, 5, 12, 30, 78, 206, 552, 1498, 4105, 11340, 31541, 88237, 248076, 700478, 1985397, 5646129, 16104378, 46056513, 132031176, 379315946, 1091890772, 3148736064, 9095091878, 26310816944, 76219704957, 221085782559, 642058752476, 1866693825362, 5432795508417

Offset: 0

Paul D. Hanna, Jul 14 2006

nonn

Equals column 0 and main diagonal of triangle A120894 (cascadence of 1+x+x^2).

			A(x) = 1 + x + 2*x^2 + 5*x^3 + 12*x^4 + 30*x^5 + 78*x^6 + 206*x^7+...
= G(x)*A(x^3*G(x)^2) where
G(x) = 1 + x + 2*x^2 + 4*x^3 + 9*x^4 + 21*x^5 + 51*x^6 + 127*x^7 +...
is the g.f. of the Motzkin numbers (A001006) so that G(x) satisfies:
G(x) = 1 + x*G(x) + x^2*G(x)^2.

Cf. A120894, A120896, A120897; A001006; variants: A092684, A092687, A120899.

{a(n)=local(A=1+x,G=1/x*serreverse(x/(1+x+x^2+x*O(x^n)))); for(i=0,n,A=G*subst(A,x,x^3*G^2 +x*O(x^n)));polcoeff(A,n,x)}

A120920 G.f. satisfies: A(x) = G(x)^3 * A(x^4G(x)^9), where G(x) is the g.f. of the number of ternary trees (A001764): G(x) = 1 + xG(x)^3.

Original entry on oeis.org

1, 3, 12, 55, 276, 1464, 8058, 45543, 262626, 1538607, 9130446, 54761628, 331403447, 2021021082, 12407102937, 76611488305, 475493441604, 2964664310319, 18560063203353, 116621922800283, 735236268006654

Offset: 0

Paul D. Hanna, Jul 17 2006

nonn

Column 0 of triangle A120919 (cascadence of (1+x)^3).

			A(x) = 1 + 3*x + 12*x^2 + 55*x^3 + 276*x^4 + 1464*x^5 + 8058*x^6 +...
= G(x)^3 * A(x^4*G(x)^9) where
G(x) = 1 + x + 3*x^2 + 12*x^3 + 55*x^4 + 273*x^5 + 1428*x^6 +...
is g.f. of A001764: G(x) = 1 + x*G(x)^3.

Cf. A120919, A120921 (cube-root), A120922, A120923; A001764; variants: A092684, A092687, A120895, A120899, A120920.

{a(n)=local(A=1+x,G=(1/x*serreverse(x/(1+3*x+3*x^2+x^3+x*O(x^n))))^(1/3)); for(i=0,n,A=G^3*subst(A,x,x^4*G^9 +x*O(x^n)));polcoeff(A,n,x)}

A120915 G.f. satisfies: A(x) = C(2x)^2 * A(x^3*C(2x)^4), where C(x) is the g.f. of the Catalan numbers (A000108).

Original entry on oeis.org

1, 4, 20, 116, 720, 4656, 30996, 210896, 1459536, 10239796, 72651184, 520328112, 3756512912, 27307671040, 199705789248, 1468209751856, 10844681408064, 80437588353600, 598867568439828, 4473784063109904, 33524058847464912

Offset: 0

Paul D. Hanna, Jul 17 2006

nonn

Column 0 of triangle A120914 (cascadence of (1+2x)^2).

			A(x) = 1 + 4*x + 20*x^2 + 116*x^3 + 720*x^4 + 4656*x^5 + 30996*x^6 +...
= C(2x)^2 * A(x^3*C(2x)^4) where
C(2x) = 1 + 2*x + 8*x^2 + 40*x^3 + 224*x^4 + 1344*x^5 + 8448*x^6 +...
and C(x) is g.f. of the Catalan numbers (A000108): C(x) = 1 + x*C(x)^2.

Cf. A120914, A120916 (square-root), A120917, A120918; A000108; variants: A092684, A092687, A120895, A120899, A120920.

{a(n)=local(A=1+x,C=(1/x*serreverse(x/(1+4*x+4*x^2+x*O(x^n))))^(1/2)); for(i=0,n,A=C^2*subst(A,x,x^3*C^4 +x*O(x^n)));polcoeff(A,n,x)}

A092685 Row sums of triangle A092683, in which the convolution of each row with {1,1} produces a triangle that, when flattened, equals the flattened form of A092683.

Original entry on oeis.org

1, 2, 5, 11, 25, 55, 120, 258, 551, 1169, 2469, 5193, 10885, 22746, 47404, 98553, 204443, 423259, 874680, 1804556, 3717348, 7647075, 15711194, 32242013, 66096274, 135366764, 276988466, 566312984, 1156974619, 2362043602

Offset: 0

Paul D. Hanna, Mar 04 2004

nonn

Cf. A092683, A092684, A092686, A092689, A120897, A120902.

{T(n,k)=if(n<0 || k>n,0, if(n==0 && k==0,1, if(n==1 && k<=1,1, if(k==n,T(n,0), T(n-1,k)+T(n-1,k+1)))))}
a(n)=sum(k=0,n,T(n,k))

{a(n)=local(A,F=1+x,d=1,G=x,H=1+x,S=ceil(log(n+1)/log(d+1))); for(i=0,n,G=x*subst(F,x,G+x*O(x^n)));for(i=0,S,H=subst(H,x,x*G^d+x*O(x^n))*G/x); A=(x*H-y*subst(H,x,x*y^d +x*O(x^n)))/(x*subst(F,x,y)-y); sum(k=0,2*n,polcoeff(polcoeff(A,n,x),k,y))} \\ Paul D. Hanna, Jul 17 2006

G.f.: A(x,y) = H(x)*(1-x)/(1-2*x), where H(x) satisfies: H(x) = H(x^2/(1-x))/(1-x) and H(x) is the g.f. of A092684. - Paul D. Hanna, Jul 17 2006

A352039 a(0) = 1; a(n) = Sum_{k=0..floor(n/3)} binomial(n-2k,k) a(k).

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 6, 9, 13, 20, 32, 51, 82, 133, 215, 346, 555, 886, 1408, 2231, 3528, 5572, 8797, 13892, 21950, 34707, 54919, 86958, 137761, 218339, 346178, 549073, 871261, 1383243, 2197542, 3494019, 5560580, 8858687, 14128865, 22560717, 36067022, 57725840

Offset: 0

Ilya Gutkovskiy, Mar 01 2022

nonn

Cf. A092684, A102547, A352041.

a[0] = 1; a[n_] := a[n] = Sum[Binomial[n - 2 k, k] a[k], {k, 0, Floor[n/3]}]; Table[a[n], {n, 0, 41}]
nmax = 41; A[] = 1; Do[A[x] = A[x^3/(1 - x)]/(1 - x) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]

G.f. A(x) satisfies: A(x) = A(x^3/(1 - x)) / (1 - x).

A352041 a(0) = 1; a(n) = Sum_{k=0..floor(n/4)} binomial(n-3k,k) a(k).

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 96, 136, 196, 285, 417, 614, 909, 1349, 2002, 2968, 4394, 6493, 9572, 14074, 20639, 30189, 44049, 64123, 93151, 135080, 195599, 282915, 408884, 590658, 853080, 1232168, 1780190, 2573059, 3721103

Offset: 0

Ilya Gutkovskiy, Mar 01 2022

nonn

Cf. A092684, A180184, A352039.

a[0] = 1; a[n_] := a[n] = Sum[Binomial[n - 3 k, k] a[k], {k, 0, Floor[n/4]}]; Table[a[n], {n, 0, 44}]
nmax = 44; A[] = 1; Do[A[x] = A[x^4/(1 - x)]/(1 - x) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]

G.f. A(x) satisfies: A(x) = A(x^4/(1 - x)) / (1 - x).

Showing 1-10 of 10 results.

cp's OEIS Frontend

A100938 Self-convolution of A092684.

Views

Author

Keywords

Comments

Crossrefs

Programs

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

A092683 Triangle, read by rows, such that the convolution of each row with {1,1} produces a triangle which, when flattened, equals this flattened form of the original triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A120899 G.f. satisfies: A(x) = C(x)^2 * A(x^3*C(x)^4), where C(x) is the g.f. of the Catalan numbers (A000108).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A120895 G.f. satisfies: A(x) = G(x)*A(x^3*G(x)^2) where G(x) is the g.f. of the Motzkin numbers (A001006).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A120920 G.f. satisfies: A(x) = G(x)^3 * A(x^4*G(x)^9), where G(x) is the g.f. of the number of ternary trees (A001764): G(x) = 1 + x*G(x)^3.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A120915 G.f. satisfies: A(x) = C(2x)^2 * A(x^3*C(2x)^4), where C(x) is the g.f. of the Catalan numbers (A000108).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A092685 Row sums of triangle A092683, in which the convolution of each row with {1,1} produces a triangle that, when flattened, equals the flattened form of A092683.

Views

Author

Keywords

Crossrefs

Programs

PARI

PARI

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.

A120895 G.f. satisfies: A(x) = G(x)A(x^3G(x)^2) where G(x) is the g.f. of the Motzkin numbers (A001006).

A120920 G.f. satisfies: A(x) = G(x)^3 * A(x^4G(x)^9), where G(x) is the g.f. of the number of ternary trees (A001764): G(x) = 1 + xG(x)^3.

A352039 a(0) = 1; a(n) = Sum_{k=0..floor(n/3)} binomial(n-2k,k) a(k).

A352041 a(0) = 1; a(n) = Sum_{k=0..floor(n/4)} binomial(n-3k,k) a(k).