The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS"). Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A004149 Generalized Catalan numbers: a(n+1) = a(n) + Sum_{k=2..n-1} a(k)a(n-1-k). (Formerly M1131) 15
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,5 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). REFERENCES N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS T. D. Noe and Seiichi Manyama, Table of n, a(n) for n = 0..2626 (first 201 terms from T. D. Noe) Andrei Asinowski, Cyril Banderier, 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] T. Doslic, D. Svrtan and D. Veljan, Enumerative aspects of secondary structures, Discr. Math., 285 (2004), 67-82. Shanzhen Gao, 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. 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. J. 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) Zhuang, Yan. A generalized Goulden-Jackson cluster method and lattice path enumeration, Discrete Mathematics 341.2 (2018): 358-379; arXiv:1508.02793 [math.CO], 2015-2018. 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 EXAMPLE 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 + ... 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 *) PROG (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 */ (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 CROSSREFS Third row of A064645. Cf. A001006, A004148. Sequence in context: A126683 A005821 A177794 * A129986 A317880 A299271 Adjacent sequences:  A004146 A004147 A004148 * A004150 A004151 A004152 KEYWORD nonn,nice AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 2 13:57 EST 2020. Contains 338877 sequences. (Running on oeis4.)