A090344 -id:A090344 - cp's OEIS frontend

A124500 Number of 1-2-3-4-5 trees with n edges and with thinning limbs. A 1-2-3-4-5 tree is an ordered tree with vertices of outdegree at most 5. A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children.

1, 1, 2, 4, 10, 25, 67, 180, 495, 1375, 3871, 10993, 31493, 90843, 263686, 769466, 2256135, 6643082, 19634705, 58232350, 173242381, 516860717, 1546035258, 4635543843, 13929569399, 41943013047, 126532961332, 382396277940

Offset: 0

Emeric Deutsch and Louis Shapiro, Nov 06 2006

nonn

The sequences corresponding to k=2 (A090344), k=3 (A124497), k=4 (A124499), k=5 (this A124500), etc. approach sequence A124344, corresponding to ordered trees with thinning limbs.

Cf. A090344, A124497, A124499, A124501, A124344.

{a(n)=local(k=5,M=1+x*O(x^n)); for(i=1,k,M=M*sum(j=0,n,binomial(i*j,j)/((i-1)*j+1)*(x^i*M^(i-1))^j)); polcoeff(M,n)} \\ Paul D. Hanna

In general, if M[k](z) is the g.f. of the 1-2-...-k trees with thinning limbs and C[k](z)=1+z*{C[k](z)}^k is the g.f. of the k-ary trees, then M[k](z)=M[k-1](z)*C[k](M[k-1]^(k-1)*z^k), M[1](z)=1/(1-z).

A124501 Number of 1-2-3-4-5-6 trees with n edges and with thinning limbs. A 1-2-3-4-5-6 tree is an ordered tree with vertices of outdegree at most 6. A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children.

Original entry on oeis.org

1, 1, 2, 4, 10, 25, 68, 186, 522, 1479, 4246, 12289, 35872, 105411, 311662, 926270, 2765778, 8292296, 24953437, 75338686, 228140842, 692733127, 2108652750, 6433255041, 19668210742, 60247367313, 184879648441, 568281131800

Offset: 0

Emeric Deutsch and Louis Shapiro, Nov 06 2006

nonn

The sequences corresponding to k=2 (A090344), k=3 (A124497), k=4 (A124499), k=5 (A124500), k=6 (this A124501), etc. approach sequence A124344, corresponding to ordered trees with thinning limbs.

Cf. A090344, A124497, A124499, A124500, A124344.

{a(n)=local(k=6,M=1+x*O(x^n)); for(i=1,k,M=M*sum(j=0,n,binomial(i*j,j)/((i-1)*j+1)*(x^i*M^(i-1))^j)); polcoeff(M,n)} \\ Paul D. Hanna

In general, if M[k](z) is the g.f. of the 1-2-...-k trees with thinning limbs and C[k](z)=1+z*{C[k](z)}^k is the g.f. of the k-ary trees, then M[k](z)=M[k-1](z)*C[k](M[k-1]^(k-1)*z^k), M[1](z)=1/(1-z).

A144700 Generalized (3,-1) Catalan numbers.

Original entry on oeis.org

1, 1, 1, 1, 2, 5, 11, 21, 38, 71, 141, 289, 591, 1195, 2410, 4897, 10051, 20763, 42996, 89139, 185170, 385809, 806349, 1689573, 3547152, 7459715, 15714655, 33161821, 70095642, 148388521, 314562189, 667682057, 1418942341

Offset: 0

Paul Barry, Sep 19 2008

Number of lattice paths in the first quadrant from (0,0) to (n,0) using only steps H=(1,0), U=(1,1) and D=(3,-1). Hankel transform has g.f. (1-x^3)/(1+x^4) (A132380 (n+3)).

G. C. Greubel, Table of n, a(n) for n = 0..1000
S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017).

Cf. A000108, A014137, A023431, A090344, A132380.

[(&+[Binomial(n-k,3*k)*Catalan(k): k in [0..Floor(n/4)]]): n in [0..40]]; // G. C. Greubel, Jun 15 2022

b[n_, m_]:=a[n, m]=Sum[Binomial[n-k,m*k]*CatalanNumber[k], {k,0,Floor[n/(m+1)]}];
A144700[n_]:= b[n,3]; (* A014137 (m=0), A090344 (m=1), A023431 (m=2) *)
Table[A144700[n], {n, 0, 40}] (* G. C. Greubel, Jun 15 2022 *)

[sum(binomial(n-k,3*k)*catalan_number(k) for k in (0..(n//4))) for n in (0..40)] # G. C. Greubel, Jun 15 2022

G.f.: (1/(1-x)) * c(x^4/(1-x)^3), where c(x) is the g.f. of A000108.
a(n) = Sum_{k=0..floor(n/4)} binomial(n-k, 3*k)*A000108(k).
(n+4)*a(n) = 2*(2*n+5)*a(n-1) - 6*(n+1)*a(n-2) + 2*(2*n-1)*a(n-3) +3*(n-2)*a(n-4) - 2*(2*n-7)*a(n-5). - R. J. Mathar, Nov 16 2011
a(n) = b(n, 3), where b(n, m) = Sum_{k=0..floor(n/(m+1))} binomial(n-k, m*k)*A000108(k). - G. C. Greubel, Jun 15 2022

A257388 Number of 4-Motzkin paths of length n with no level steps at odd level.

Original entry on oeis.org

1, 4, 17, 72, 306, 1304, 5573, 23888, 102702, 442904, 1915978, 8314480, 36195236, 158067312, 692475053, 3043191200, 13415404246, 59321085720, 263100680926, 1170347803440, 5221037429948, 23356788588752, 104772374565666, 471214329434208, 2124649562373708, 9603094073668208

Offset: 0

José Luis Ramírez Ramírez, Apr 21 2015

nonn

			For n=2 we have 17 paths: H(1)H(1), H(1)H(2), H(1)H(3), H(1)H(4), H(2)H(1), H(2)H(2), H(2)H(3), H(2)H(4), H(3)H(1), H(3)H(2), H(3)H(3), H(3)H(4), H(4)H(1), H(4)H(2), H(4)H(3), H(4)H(4) and UD.

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A086622, A090344, A104498, A257178.

CoefficientList[Series[(1-4*x-Sqrt[(1-4*x)*(1-4*x-4*x^2)])/(2*x^2*(1-4*x)), {x, 0, 20}], x] (* Vaclav Kotesovec, Apr 22 2015 *)

x='x+O('x^50); Vec((1-4*x-sqrt((1-4*x)*(1-4*x-4*x^2)))/(2*x^2*(1-4*x))) \\ G. C. Greubel, Apr 08 2017

a(n) = Sum_{i=0..floor(n/2)}4^(n-2i)*C(i)*binomial(n-i,i), where C(n) is the n-th Catalan number A000108.
G.f.: (1-4*x-sqrt((1-4*x)*(1-4*x-4*x^2)))/(2*x^2*(1-4*x)).
a(n) ~ sqrt(58+41*sqrt(2)) * 2^(n+1/2) * (1+sqrt(2))^n / (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Apr 22 2015
Conjecture: (n+2)*a(n) +8*(-n-1)*a(n-1) +4*(3*n+1)*a(n-2) +8*(2*n-3)*a(n-3)=0. - R. J. Mathar, Sep 24 2016
G.f. A(x) satisfies: A(x) = 1/(1 - 4*x) + x^2 * A(x)^2. - Ilya Gutkovskiy, Jun 30 2020

A257389 Number of 3-generalized Motzkin paths of length n with no level steps H=(3,0) at odd level.

Original entry on oeis.org

1, 0, 1, 1, 2, 2, 6, 6, 17, 21, 54, 74, 183, 272, 644, 1025, 2342, 3928, 8734, 15264, 33227, 59989, 128484, 238008, 503563, 952038, 1995955, 3835381, 7987092, 15548654, 32223061, 63388488, 130918071, 259724317, 535168956, 1069025128

Offset: 0

José Luis Ramírez Ramírez, Apr 21 2015

nonn

			For n=6 we have 6 paths: UDUDUD, H3H3, UUDUDD, UUUDDD, UDUUDD and UUDDUD, where H3=(3,0).

Robert Israel, Table of n, a(n) for n = 0..3087

Cf. A000108, A090344, A086622, A257178, A007317, A064613, A104455, A104498.

f:= gfun:-rectoproc({(2 + n)*a(n) + (14 + 4*n)*a(n + 1) + (-10 - 2*n)*a(n + 3) + (-20 - 4*n)*a(n + 4) + (8 + n)*a(n + 6), a(0) = 1, a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 2, a(5) = 2},a(n),remember):
map(f, [$0..100]); # Robert Israel, Nov 04 2019

a(n):=sum(((-1)^(n-3*k)+1)*((binomial((n-k)/2,k) )*(binomial(n-3*k,(n-3*k)/2))/((n-3*k+2))),k,0,(n)/3); /* Vladimir Kruchinin, Apr 02 2016 */

G.f.: (1-x^3-sqrt((1-x^3)*(1-4*x^2-x^3)))/(2*x^2*(1-x^3)).
a(n) = Sum_{k=0..n/3}(((-1)^(n-3*k)+1)*(binomial((n-k)/2,k)*(binomial(n-3*k,(n-3*k)/2))/((n-3*k+2)))). - Vladimir Kruchinin, Apr 02 2016
(2 + n)*a(n) + (14 + 4*n)*a(n + 1) + (-10 - 2*n)*a(n + 3) + (-20 - 4*n)*a(n + 4) + (8 + n)*a(n + 6) = 0. - Robert Israel, Nov 04 2019

A257515 Number of 3-generalized 2-Motzkin paths of length n with no level steps H=(3,0) at odd level.

Original entry on oeis.org

1, 0, 1, 2, 2, 4, 9, 12, 26, 48, 90, 172, 348, 664, 1349, 2680, 5438, 10976, 22510, 45900, 94700, 195032, 404442, 838824, 1748308, 3646368, 7632628, 15994232, 33606168, 70699504, 149050669, 314625264, 665280246, 1408436672, 2986069782, 6337988876

Offset: 0

José Luis Ramírez Ramírez, Apr 27 2015

nonn

			For n=6 we have 9 paths: UDUDUD, H3H3 (4 options), UUDUDD, UUUDDD, UDUUDD and UUDDUD, where H3=(3,0).

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Cf. A090344, A086622, A257178, A257388, A007317, A064613, A104455, A104498, A257389.

CoefficientList[Series[(1-2*x^3-Sqrt[(1-2x^3)*(1-4*x^2-2*x^3)])/(2*x^2*(1-2*x^3)), {x, 0, 30}], x] (* Vaclav Kotesovec, Apr 28 2015 *)

a(n):=sum((binomial(2*m,m)/(m+1)*(if mod(n+m,3)=0 then 2^((n-2*m)/3)* binomial((m+n)/3,m) else 0)),m,0,n); /* Vladimir Kruchinin, Mar 07 2016 */

seq(n)={Vec((1-2*x^3-sqrt((1-2*x^3)*(1-4*x^2-2*x^3) + O(x^(3+n))))/(2*x^2*(1-2*x^3)))} \\ Andrew Howroyd, May 01 2020

G.f.: (1-2*x^3-sqrt((1-2x^3)*(1-4*x^2-2*x^3)))/(2*x^2*(1-2*x^3)).

Conjecture: (n+2)*a(n) +(n+1)*a(n-1) +(n+4)*a(n-2) +4*(-2*n+3)*a(n-3) +4*(-6*n+17)*a(n-4) +4*(-3*n+10)*a(n-5) +4*(3*n-11)*a(n-6) +4*(11*n-50)*a(n-7) +20*(n-6)*a(n-8)=0. - R. J. Mathar, Jun 07 2016

Terms a(31) and beyond from Andrew Howroyd, May 01 2020

A364588 G.f. satisfies A(x) = 1/(1-x) + x^2*A(x)^4.

Original entry on oeis.org

1, 1, 2, 5, 15, 49, 170, 613, 2275, 8629, 33301, 130333, 516077, 2063685, 8321892, 33803161, 138181521, 568031297, 2346668400, 9737766513, 40569611691, 169632827345, 711611670532, 2994165070045, 12632782541053, 53433933353885, 226540298098019

Offset: 0

Seiichi Manyama, Jul 29 2023

Cf. A049130, A090344.

Cf. A226974, A349289, A364591.

a(n) = sum(k=0, n\2, binomial(n+k, 3*k)*binomial(4*k,k)/(3*k+1));

a(n) = Sum_{k=0..floor(n/2)} binomial(n+k,3*k) * binomial(4*k,k) / (3*k+1).

A114576 Triangle read by rows: T(n,k) is number of Motzkin paths of length n having k UH's, where U=(1,1), H=(1,0) (0<=k<=floor(n/3)).

Original entry on oeis.org

1, 1, 2, 3, 1, 6, 3, 11, 10, 23, 26, 2, 47, 70, 10, 102, 176, 45, 221, 449, 160, 5, 493, 1121, 539, 35, 1105, 2817, 1680, 196, 2516, 7031, 5082, 868, 14, 5763, 17604, 14856, 3486, 126, 13328, 43996, 42660, 12810, 840, 30995, 110147, 120338, 44640, 4410, 42

Offset: 0

Emeric Deutsch, Dec 09 2005

Row n contains 1+floor(n/3) terms. Row sums are the Motzkin numbers (A001006). Column 0 yields A090344. Sum(k*T(n,k),k=0..floor(n/3))=A014531(n-2).

			T(4,1)=3 because we have H(UH)D, (UH)DH and (UH)HD, where U=(1,1), H=(1,0), D=(1,-1) (the UH's are shown between parentheses).
Triangle begins:
1;
1;
2;
3,1;
6,3;
11,10;
23,26,2;
47,70,10;

Cf. A001006, A090344, A014531.

G:=(1-z-sqrt(1-2*z-3*z^2-4*z^3*t+4*z^3))/2/z^2/(1-z+t*z): Gser:=simplify(series(G,z=0,20)): P[0]:=1: for n from 1 to 16 do P[n]:=coeff(Gser,z^n) od: for n from 0 to 16 do seq(coeff(t*P[n],t^j),j=1..1+floor(n/3)) od; # yields sequence in triangular form

G.f.=[1-z-sqrt(1-2z-3z^2-4tz^3+4z^3)]/[2(1-z+tz)z^2].

A118677 Number of Motzkin paths of length n in 3D with no level steps at odd level.

Original entry on oeis.org

1, 2, 6, 18, 60, 202, 718, 2600, 9748, 37270, 146058, 582548, 2367028, 9761890, 40844168, 173001018, 741193056, 3207480526, 14008373662, 61683982696, 273658651700, 1222314257450, 5493414465900, 24828463984518

Offset: 0

Max Alekseyev, May 19 2006

nonn

Cf. A090344.

EXPCONV of A090344 with itself, i.e. a(n) = sum_{k=0}^n binomial(n,k)*A090344(k)*A090344(n-k)

A337187 a(n) = 1 + Sum_{k=0..n-2} binomial(n-2,k) * a(k) * a(n-k-2).

Original entry on oeis.org

1, 1, 2, 3, 7, 19, 63, 229, 955, 4407, 22445, 124249, 746003, 4821287, 33394193, 246652725, 1935828995, 16086138151, 141100295557, 1302780182449, 12630092274099, 128275445380247, 1362029496267529, 15090795795916493, 174167341456580947, 2090520625244752407

Offset: 0

Ilya Gutkovskiy, Jan 29 2021

nonn

Cf. A007558, A054687, A090344.

a[n_] := a[n] = 1 + Sum[Binomial[n - 2, k] a[k] a[n - k - 2], {k, 0, n - 2}]; Table[a[n], {n, 0, 25}]

E.g.f. A(x) satisfies: A''(x) = exp(x) + A(x)^2.

cp's OEIS Frontend

A124500 Number of 1-2-3-4-5 trees with n edges and with thinning limbs. A 1-2-3-4-5 tree is an ordered tree with vertices of outdegree at most 5. A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

A124501 Number of 1-2-3-4-5-6 trees with n edges and with thinning limbs. A 1-2-3-4-5-6 tree is an ordered tree with vertices of outdegree at most 6. A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

A144700 Generalized (3,-1) Catalan numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A257388 Number of 4-Motzkin paths of length n with no level steps at odd level.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A257389 Number of 3-generalized Motzkin paths of length n with no level steps H=(3,0) at odd level.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Maxima

Formula

A257515 Number of 3-generalized 2-Motzkin paths of length n with no level steps H=(3,0) at odd level.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

Extensions

A364588 G.f. satisfies A(x) = 1/(1-x) + x^2*A(x)^4.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A114576 Triangle read by rows: T(n,k) is number of Motzkin paths of length n having k UH's, where U=(1,1), H=(1,0) (0<=k<=floor(n/3)).

Views

Author

Keywords

Comments

Examples