A086622 -id:A086622 - cp's OEIS frontend

A090344 Number of Motzkin paths of length n with no level steps at odd level.

1, 1, 2, 3, 6, 11, 23, 47, 102, 221, 493, 1105, 2516, 5763, 13328, 30995, 72556, 170655, 403351, 957135, 2279948, 5449013, 13063596, 31406517, 75701508, 182902337, 442885683, 1074604289, 2612341856, 6361782007, 15518343597, 37912613631, 92758314874

Offset: 0

Emeric Deutsch, Jan 28 2004

nonn

a(n) = number of Motzkin paths of length n that avoid UF. Example: a(3) counts FFF, UDF, FUD but not UFD. - David Callan, Jul 15 2004

Also, number of 1-2 trees with n edges and with thinning limbs. A 1-2 tree is an ordered tree with vertices of outdegree at most 2. A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children. - Emeric Deutsch and Louis Shapiro, Nov 04 2006

			a(3)=3 because we have HHH, HUD and UDH, where U=(1,1), D=(1,-1) and H=(1,0).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.
Rui Duarte and António Guedes de Oliveira, Generating functions of lattice paths, Univ. do Porto (Portugal 2023).

Cf. A001006, A086622, A098474, A124344, A124497.

Cf. A014137, A023431, A144700.

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

C:=x->(1-sqrt(1-4*x))/2/x: G:=C(z^2/(1-z))/(1-z): Gser:=series(G,z=0,40): seq(coeff(Gser,z,n),n=0..36);
# second Maple program:
a:= proc(n) option remember; `if`(n<3, (n^2-n+2)/2,
     ((2*n+2)*a(n-1) -(4*n-6)*a(n-3) +(3*n-4)*a(n-2))/(n+2))
    end:
seq(a(n), n=0..40); # Alois P. Heinz, May 17 2013

Table[HypergeometricPFQ[{1/2, (1-n)/2, -n/2}, {2, -n}, -16], {n, 0, 40}] (* Jean-François Alcover, Feb 20 2015, after Paul Barry *)

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

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

G.f.: (1-x-sqrt(1-2*x-3*x^2+4*x^3))/(2*x^2*(1-x)).
G.f. satisfies: A(x) = 1/(1-x) + x^2*A(x)^2. - Paul D. Hanna, Jun 24 2012
D-finite with recurrence (n+2)*a(n) = 2*(n+1)*a(n-1) + (3*n-4)*a(n-2) - 2*(2*n-3)*a(n-3). - Vladeta Jovovic, Sep 11 2004
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*binomial(2*k, k)/(k+1). - Paul Barry, Nov 13 2004
a(n) = 1 + Sum_{k=1..n-1} a(k-1)*a(n-k-1). - Henry Bottomley, Feb 22 2005
G.f.: 1/(1-x-x^2/(1-x^2/(1-x-x^2/(1-x^2/(1-x-x^2/(1-x^2/(1-... (continued fraction). - Paul Barry, Apr 08 2009
With M = an infinite tridiagonal matrix with all 1's in the super and subdiagonals and [1,0,1,0,1,0,...] in the main diagonal and V = vector [1,0,0,0,...] with the rest zeros, the sequence starting with offset 1 = leftmost column iterates of M*V. - Gary W. Adamson, Jun 08 2011
Recurrence (an alternative): (n+2)*a(n) = 3*(n+1)*a(n-1) + (n-4)*a(n-2) - (7*n-13)*a(n-3) + 2*(2*n-5)*a(n-4), n>=4. - Fung Lam, Apr 01 2014
Asymptotics: a(n) ~ (8/(sqrt(17)-1))^n*( 1/17^(1/4) + 17^(1/4) )*17 /(16*sqrt(Pi*n^3)). - Fung Lam, Apr 01 2014
a(n) = 2*A026569(n) + A026569(n+1)/2 - A026569(n+2)/2. - Mark van Hoeij, Nov 29 2024

A009531 Expansion of the e.g.f. sin(x)*(1+x).

Original entry on oeis.org

0, 1, 2, -1, -4, 1, 6, -1, -8, 1, 10, -1, -12, 1, 14, -1, -16, 1, 18, -1, -20, 1, 22, -1, -24, 1, 26, -1, -28, 1, 30, -1, -32, 1, 34, -1, -36, 1, 38, -1, -40, 1, 42, -1, -44, 1, 46, -1, -48, 1, 50, -1, -52, 1, 54, -1, -56, 1, 58, -1, -60, 1, 62, -1, -64, 1, 66, -1, -68, 1, 70, -1, -72, 1, 74, -1, -76, 1, 78, -1, -80

Offset: 0

R. H. Hardin

Murat Sahin and Elif Tan, Conditional (strong) divisibility sequences, Fib. Q., 56 (No. 1, 2018), 18-31.

Antti Karttunen, Table of n, a(n) for n = 0..16384
Index entries for linear recurrences with constant coefficients, signature (0,-2,0,-1).

Cf. A009001, A029578, A049240.

[(((2*n+3-(-1)^n)/2)*(-1)^((2*n+5-(-1)^n) div 4)+((2*n-1-(-1)^n) div 2)*(-1)^((6*n+5-(-1)^n) div 4))/2: n in [0..90]]; // Vincenzo Librandi, Jul 19 2015

CoefficientList[Series[x*(1+x)^2/(1+x^2)^2, {x, 0, 100}], x] (* Vaclav Kotesovec, Oct 03 2014 *)

concat(0, Vec(x*(1+x)^2/(1+x^2)^2 + O(x^80))) \\ Michel Marcus, Oct 03 2014

A009531(n) = (((n^(n+1)) % (n+1)) * ((-1)^((n-1)\2))); \\ Antti Karttunen, Nov 02 2017, after Henry Bottomley's formula.

A009531(n) = (lift(Mod(n, n+1)^(n+1)) * ((-1)^((n-1)\2))); \\ (like above, but quicker) - Antti Karttunen, Nov 02 2017

There's an obvious formula for the n-th term!
G.f.: x*(1+x)^2/(1+x^2)^2.
abs(a(n)) = Sum_{k=0..floor((n-1)/2)} (C(n-k-1, k) mod 2)*(-1)^k*2^A000120(n-2k-1). - Paul Barry, Jan 06 2005
a(n) = (n^(n+1) mod (n+1)) * (-1)^[(n-1)/2] = a(n-1)-a(n-2)+(-1)^n*a(n-1) = -2a(n-2)-a(n-4). - Henry Bottomley, May 07 2005
a(n+2) is the Hankel transform of A086622(n+1). - Paul Barry, Nov 06 2007
E.g.f.: sin(x)*(1+x)=x*Q(0); Q(k)=1+x/(1-x/(x-2*(k+1)*(2k+3)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 18 2011
a(n) = sin(Pi*n/2)-n*cos(Pi*n/2). - Vaclav Kotesovec, Oct 03 2014
a(n) = (((2*n+3-(-1)^n)/2)*(-1)^((2*n+5-(-1)^n)/4)+((2*n-1-(-1)^n)/2)*(-1)^((6*n+5-(-1)^n)/4))/2. - Luce ETIENNE, Jul 18 2015

A086620 Symmetric square table of coefficients, read by antidiagonals, where T(n,k) is the coefficient of x^ny^k in f(x,y) that satisfies f(x,y) = 1/(1-x-y) + xyf(x,y)^2.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 5, 5, 1, 1, 7, 14, 7, 1, 1, 9, 28, 28, 9, 1, 1, 11, 47, 79, 47, 11, 1, 1, 13, 71, 175, 175, 71, 13, 1, 1, 15, 100, 331, 504, 331, 100, 15, 1, 1, 17, 134, 562, 1196, 1196, 562, 134, 17, 1, 1, 19, 173, 883, 2464, 3514, 2464, 883, 173, 19, 1, 1, 21, 217

Offset: 0

Paul D. Hanna, Jul 24 2003

Determinants of upper left n X n matrices results in A086619: {1,2,10,150,7650,1438200,1051324200,...}, which is the products of the first n terms of the binomial transform of Catalan numbers (A007317): {1,2,5,15,51,188,731,2950,...}.

			Rows begin:
1,_1,__1,__1,___1,____1,____1,_____1, ...
1,_3,__5,__7,___9,___11,___13,____15, ...
1,_5,_14,_28,__47,___71,__100,___134, ...
1,_7,_28,_79,_175,__331,__562,___883, ...
1,_9,_47,175,_504,_1196,_2464,__4572, ...
1,11,_71,331,1196,_3514,_8764,_19244, ...
1,13,100,562,2464,_8764,26172,_67740, ...
1,15,134,883,4572,19244,67740,204831, ...

Cf. A086621 (diagonal), A086622 (antidiagonal sums), A086619 (determinants).

Contribution from Paul Barry, Feb 04 2009: (Start)
T(n,k)=sum{j=0..n+k, C(k,j-k)*C(n+2k-j,k)*if(k<=j,A000108(n-k),0)};
Regarded as a number triangle read by row, columns are generated by sum{j=0..k, C(k,j)*A000108(j)*x^j}*x^k/(1-x)^(k+1). (End)

A086621 Main diagonal of square table A086620 of coefficients, T(n,k), of x^ny^k in f(x,y) that satisfies f(x,y) = 1/(1-x-y) + xyf(x,y)^2.

Original entry on oeis.org

1, 3, 14, 79, 504, 3514, 26172, 204831, 1664696, 13930840, 119312544, 1041227642, 9228614836, 82867255956, 752405060536, 6897376441167, 63760133568096, 593763928313128, 5565678569009328, 52475976165495960, 497376657383374560, 4736680863568248480, 45304174896889357440

Offset: 0

Paul D. Hanna, Jul 24 2003

nonn

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

Cf. A086620 (table), A086622 (antidiagonal sums).

re:= sumtools:-sumrecursion(binomial(n,j) * binomial(2*n-j,n) * binomial(2*j,j)/(j+1),j,a(n)); # re = Mathar's recurrence
f:= gfun:-rectoproc({re = 0, a(0)=1, a(1)=3, a(2)=14}, a(n), remember): map(f, [$0..20]); # Georg Fischer, Oct 23 2022

a(n) = {sum(j=0, n, binomial(n,j)*binomial(2*n-j, n)*binomial(2*j, j)/(j+1))} \\ Andrew Howroyd, Apr 11 2021

a(n) = Sum_{j=0..n} binomial(n,j) * binomial(2*n-j,n) * binomial(2*j,j)/(j+1). - Andrew Howroyd, Apr 11 2021
D-finite with recurrence n*(n-1)*(n+1)^2*a(n) -2*n*(n-1) *(4*n+3) *(2*n-1) *a(n-1) +4*(n-1) *(16*n^3-20*n^2-13*n+14) *a(n-2) -4*(n-2) *(4*n-9) *(4*n-3) *(n+1) *a(n-3)=0. - R. J. Mathar, Nov 02 2021
a(n) ~ sqrt(5) * 2^(2*n - 3/2) * phi^(2*n + 5/2) / (Pi * n^2), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Nov 19 2021

Terms a(18) and beyond from Andrew Howroyd, Apr 11 2021

A257178 Number of 3-Motzkin paths of length n with no level steps at odd level.

Original entry on oeis.org

1, 3, 10, 33, 110, 369, 1247, 4245, 14558, 50295, 175029, 613467, 2165100, 7692345, 27504600, 98941185, 357952580, 1301960925, 4759282415, 17478557925, 64468072820, 238736987535, 887359113700, 3309489922743, 12381998910700, 46460457776739

Offset: 0

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

nonn

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

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

Cf. A090344, A086622.

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

Vec((1-3*x-sqrt((1-3*x)*(1-3*x-4*x^2)))/(2*x^2*(1-3*x)) + O(x^50)) \\ G. C. Greubel, Feb 05 2017

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

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

cp's OEIS Frontend

A090344 Number of Motzkin paths of length n with no level steps at odd level.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A009531 Expansion of the e.g.f. sin(x)*(1+x).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

PARI

Formula

A086620 Symmetric square table of coefficients, read by antidiagonals, where T(n,k) is the coefficient of x^n*y^k in f(x,y) that satisfies f(x,y) = 1/(1-x-y) + xy*f(x,y)^2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A086621 Main diagonal of square table A086620 of coefficients, T(n,k), of x^n*y^k in f(x,y) that satisfies f(x,y) = 1/(1-x-y) + xy*f(x,y)^2.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

A257178 Number of 3-Motzkin paths of length n with no level steps at odd level.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

A086620 Symmetric square table of coefficients, read by antidiagonals, where T(n,k) is the coefficient of x^ny^k in f(x,y) that satisfies f(x,y) = 1/(1-x-y) + xyf(x,y)^2.

A086621 Main diagonal of square table A086620 of coefficients, T(n,k), of x^ny^k in f(x,y) that satisfies f(x,y) = 1/(1-x-y) + xyf(x,y)^2.