A004149 Generalized Catalan numbers: a(n+1) = a(n) + Sum_{k=2..n-1} a(k)*a(n-1-k).

1, 1, 1, 1, 2, 4, 8, 16, 33, 69, 146, 312, 673, 1463, 3202, 7050, 15605, 34705, 77511, 173779, 390966, 882376, 1997211, 4532593, 10311720, 23512376, 53724350, 122995968, 282096693, 648097855, 1491322824, 3436755328, 7931085771

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

Number of Motzkin paths of length n-1 (n>=1) with no peaks and no valleys, i.e., no UD's and no DU's, where U=(1,1) and D=(1,-1). Example: a(7)=16 because there are 17 peakless Motzkin paths of length 6 (see A004148) of which only UHDUHD has a valley (here H=(1,0)). - Emeric Deutsch, Jan 08 2004

a(n+2) = number of Motzkin n-paths that avoid both UU and DD = number of Motzkin n-paths that avoid both UU and UFU. Example: a(7)=16 since of the 21 Motzkin 5-paths, only FUUDD, UFUDD, UUDDF, UUDFD, UUFDD contain a UU or DD (or both). Likewise, only FUUDD, UFUDD, UUDDF, UUDFD, UUFDD contain a UU or UFU. - David Callan, Jul 15 2004

Number of peakless Motzkin paths of length n without UHD's; here U=(1,1), H=(1,0), and D=(1,-1). Example: a(4)=2 because we have HHHH and UHHD.

a(n) = A190172(n,0).

Examples

			G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 4*x^5 + 8*x^6 + 16*x^7 + 33*x^8 + 69*x^9 + ...
		

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..2626 (first 201 terms from T. D. Noe)
• Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
• Paul Barry, Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials, arXiv:1910.00875 [math.CO], 2019.
• M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210; arXiv:math/0205301 [math.CO], 2002.
• M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
• Tomislav Došlić, Dragutin Svrtan, and Darko Veljan, Enumerative aspects of secondary structures, Discr. Math., 285 (2004), 67-82.
• Shanzhen Gao and Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science (Sequence 8 mentions a g.f. that gives a sequence that is similar to this sequence but without the first term).
• Emanuele Munarini, Combinatorial properties of the antichains of a garland, Integers, 9 (2009), 353-374.
• Helmut Prodinger, Motzkin paths of bounded height with two forbidden contiguous subwords of length two, arXiv:2310.12497 [math.CO], 2023.
• Helmut Prodinger, Cornerless, peakless, valleyless Motzkin paths (regular and skew) and applications to bargraphs, arXiv:2501.13645 [math.CO], 2025. See p. 8.
• P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.
• P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers [Corrected annotated scanned copy]
• E. J. Janse van Rensburg, Adsorbing bargraph paths in a q-wedge, Journal of Physics A, v.38 n.40, 8505-8525.
• M. S. Waterman, Home Page (contains copies of his papers)
• Yan Zhuang, A generalized Goulden-Jackson cluster method and lattice path enumeration, Discrete Mathematics 341.2 (2018): 358-379; arXiv:1508.02793 [math.CO], 2015-2018.

Crossrefs

Third row of A064645.

Cf. A001006, A004148.

Programs

Haskell

a004149 n = a004149_list !! n
a004149_list = 1 : 1 : 1 : f [1,1,1] where
   f xs = y : f (y : xs) where
     y = head xs + sum (zipWith (*) (init $ init $ tail xs) (reverse xs))
-- Reinhard Zumkeller, Nov 13 2012

Maple

For Maple code producing the g.f. see A004148.
# Alternative:
p:= gfun:-rectoproc({(n-1)*a(n)+(2*n+1)*a(n+1)+(-n-2)*a(n+2)+(-5-n)*a(n+4)+(-13-2*n)*a(n+5)+(n+8)*a(n+6), a(0) = 1, a(1) = 1, a(2) = 1, a(3) = 1, a(4) = 2, a(5) = 4},a(n),remember):
map(p, [$0..100]); # Robert Israel, May 07 2015

Mathematica

a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-2-k ], {k, 2, n-2} ];
CoefficientList[Series[2/(1-x+x^2+x^3+Sqrt[(1-x^4)(1-2x-x^2)]),{x,0,40}],x] (* Harvey P. Dale, Aug 09 2017 *)

PARI

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

Formula

G.f.: 2/(1 - z + z^2 + z^3 + sqrt((1-z^4)(1-2z-z^2))). - Emeric Deutsch, Jan 08 2004

G.f.: 1/(1-x-x^4/(1-x-x^2-x^3-x^4/(1-x-x^2-x^3-x^4/(1-... (continued fraction). - Paul Barry, May 22 2009

D-finite with recurrence: (n+2)*a(n) = (2*n+1)*a(n-1) + (n-1)*a(n-2) + (n-4)*a(n-4) - (2*n-11)*a(n-5) - (n-7)*a(n-6). - Vaclav Kotesovec, Aug 10 2013

a(n) ~ (1+sqrt(2))^(n+1/2)/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 10 2013

G.f. g(x) satisfies x^2*g^2 - (1-x+x^2+x^3)*g + 1 = 0 and

(x^4-1)*(x^2+2*x-1)*x*g'(x) - (x^3-x+2)*(x^3+x^2+x-1)*g(x) + 4*x^3+2*x^2-2 = 0. - Robert Israel, May 07 2015

0 = a(n)*(+a(n+1) + 5*a(n+2) - 4*a(n+3) - 7*a(n+5) - 17*a(n+6) + 10*a(n+7)) + a(n+1)*(-a(n+1) + 6*a(n+2) - 5*a(n+3) + 5*a(n+4) + 2*a(n+5) - 36*a(n+6) + 17*a(n+7)) + a(n+2)*(+a(n+2) + a(n+3) + 7*a(n+4) + 24*a(n+5) - 2*a(n+6) - 7*a(n+7)) + a(n+3)*(-2*a(n+4) - 7*a(n+5) + 5*a(n+6)) + a(n+4)*(+a(n+5) + 5*a(n+6) - 4*a(n+7)) + a(n+5)*(-a(n+5) + 6*a(n+6) - 5*a(n+7)) + a(n+6)*(+a(n+6) + a(n+7)) for all n>=0. - Michael Somos, Jan 09 2017

G.f.: 1/G(x), with G(x)=1-(x-x^3)/(1-x^2/G(x)) (continued fraction). - Nikolaos Pantelidis, Jan 11 2023