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

A023431 Generalized Catalan Numbers x^3A(x)^2 + (x-1)A(x) + 1 =0.

Original entry on oeis.org

1, 1, 1, 2, 4, 7, 13, 26, 52, 104, 212, 438, 910, 1903, 4009, 8494, 18080, 38656, 82988, 178802, 386490, 837928, 1821664, 3970282, 8673258, 18987930, 41652382, 91539466, 201525238, 444379907, 981384125, 2170416738, 4806513660

Offset: 0

Olivier Gérard

Essentially the same as A025246.
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=(2,-1). E.g. a(5)=7 because we have HHHHH, HHUD, HUDH, HUHD, UDHH, UHDH and UHHD. - Emeric Deutsch, Dec 25 2003
Also number of peakless Motzkin paths of length n with no double rises; in other words, Motzkin paths of length n with no UD's and no UU's, where U=(1,1) and D=(1,-1). E.g. a(5)=7 because we have HHHHH, HHUHD, HUHDH, HUHHD, UHDHH, UHHDH and UHHHD, where H=(1,0). - Emeric Deutsch, Jan 09 2004
Series reversion of g.f. A(x) is -A(-x) (if offset 1). - Michael Somos, Jul 13 2003
Hankel transform is A010892(n+1). [From Paul Barry, Sep 19 2008]
Number of FU_{k}-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are P-equivalent iff the positions of pattern P are identical in these paths. This also works for U_{k}F-equivalence classes. - Sergey Kirgizov, Apr 08 2018

			G.f. = 1 + x + x^2 + 2*x^3 + 4*x^4 + 7*x^5 + 13*x^6 + 26*x^7 + 52*x^8 + 104*x^9 + ...

Reinhard Zumkeller, 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).
Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
Paul Barry, Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018.
Paul Barry, Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials, arXiv:1910.00875 [math.CO], 2019.
Paul Barry, Elliptic Curves, Riordan arrays and Lattice Paths, arXiv:2507.16765 [math.CO], 2025. See p. 16.
Johann Cigler, Some nice Hankel determinants, arXiv preprint arXiv:1109.1449 [math.CO], 2011.
Shalosh B. Ekhad and Mingjia Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017)
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 666
Feihu Liu, Ying Wang, Yingrui Zhang, and Zihao Zhang, Hankel Determinants for Convolution of Power Series: An Extension of Cigler's Results, arXiv:2503.17187 [math.CO], 2025. See p. 9.
K. Park and G.-S. Cheon, Lattice path counting with a bounded strip restriction
Helmut Prodinger, Motzkin paths of bounded height with two forbidden contiguous subwords of length two, arXiv:2310.12497 [math.CO], 2023.

Cf. A000108, A001006, A004148, A006318, A025246.

Cf. A014137, A090344, A144700.

a023431 n = a023431_list !! n
a023431_list = 1 : 1 : f [1,1] where
   f xs'@(x:_:xs) = y : f (y : xs') where
     y = x + sum (zipWith (*) xs $ reverse $ xs')
-- Reinhard Zumkeller, Nov 13 2012

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

a := n -> hypergeom([1/3 - n/3, 2/3 - n/3, -n/3], [2, -n], 27):
seq(simplify(a(n)), n = 0..32); # Peter Luschny, Jun 15 2022

a[0]=1; a[n_]:= a[n]= a[n-1] + Sum[a[k]*a[n-3-k], {k, 0, n-3}];
Table[a[n], {n,0,40}]

{a(n) = polcoeff( (1 - x - sqrt((1-x)^2 - 4*x^3 + x^4 * O(x^n))) / 2, n+3)}; /* Michael Somos, Jul 13 2003 */

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

G.f.: (1 - x - sqrt((1-x)^2 - 4*x^3)) / (2*x^3) = A(x). y = x * A(x) satisfies 0 = x - y + x*y + (x*y)^2. - Michael Somos, Jul 13 2003
a(n+1) = a(n) + a(0)*a(n-2) + a(1)*a(n-3) + ... + a(n-2)*a(0). - Michael Somos, Jul 13 2003
a(n) = A025246(n+3). - Michael Somos, Jan 20 2004
G.f.: (1/(1-x))*c(x^3/(1-x)^2), c(x) the g.f. of A000108. - From Paul Barry, Sep 19 2008
From Paul Barry, May 22 2009: (Start)
G.f.: 1/(1-x-x^3/(1-x-x^3/(1-x-x^3/(1-x-x^3/(1-... (continued fraction).
a(n) = Sum_{k=0..floor(n/3)} binomial(n-k, 2*k)*A000108(k). (End)
(n+3)*a(n) = (2*n+3)*a(n-1) - n*a(n-2) + 2*(2*n-3)*a(n-3). - R. J. Mathar, Nov 26 2012
0 = a(n)*(16*a(n+1) - 10*a(n+2) + 32*a(n+3) - 22*a(n+4)) + a(n+1)*(2*a(n+1) - 15*a(n+2) + 9*a(n+3) + 4*a(n+4)) + a(n+2)*(a(n+2) + 2*a(n+3) - 5*a(n+4)) + a(n+3)*(a(n+3) + a(n+4)) if n>=0. - Michael Somos, Jan 30 2014
a(n) ~ (8 + 12*r^2 + 5*r) * sqrt(r^2 - 4*r + 3) / (4 * sqrt(Pi) * n^(3/2) * r^n), where r = 0.432040800333095789... is the real root of the equation -1 + 2*r - r^2 + 4*r^3 = 0. - Vaclav Kotesovec, Jun 15 2022
a(n) = hypergeom([(1 - n)/3, (2 - n)/3, -n/3], [2, -n], 27). - Peter Luschny, Jun 15 2022

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

A023431 Generalized Catalan Numbers x^3A(x)^2 + (x-1)A(x) + 1 =0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

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

A023431 Generalized Catalan Numbers x^3*A(x)^2 + (x-1)*A(x) + 1 =0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

A023431 Generalized Catalan Numbers x^3A(x)^2 + (x-1)A(x) + 1 =0.