|
%I M1131 #108 Oct 29 2023 21:00:30
%S 1,1,1,1,2,4,8,16,33,69,146,312,673,1463,3202,7050,15605,34705,77511,
%T 173779,390966,882376,1997211,4532593,10311720,23512376,53724350,
%U 122995968,282096693,648097855,1491322824,3436755328,7931085771
%N Generalized Catalan numbers: a(n+1) = a(n) + Sum_{k=2..n-1} a(k)a(n-1-k).
%C 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
%C 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
%C 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.
%C a(n) = A190172(n,0).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Seiichi Manyama, <a href="/A004149/b004149.txt">Table of n, a(n) for n = 0..2626</a> (first 201 terms from T. D. Noe)
%H Andrei Asinowski, Cyril Banderier, and Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, (2019).
%H Paul Barry, <a href="https://arxiv.org/abs/1910.00875">Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials</a>, arXiv:1910.00875 [math.CO], 2019.
%H M. Bernstein and N. J. A. Sloane, <a href="https://arxiv.org/abs/math/0205301">Some canonical sequences of integers</a>, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210; arXiv:math/0205301 [math.CO], 2002.
%H M. Bernstein and N. J. A. Sloane, <a href="/A003633/a003633_1.pdf">Some canonical sequences of integers</a>, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
%H T. Doslic, D. Svrtan and D. Veljan, <a href="http://dx.doi.org/10.1016/j.disc.2004.04.001">Enumerative aspects of secondary structures</a>, Discr. Math., 285 (2004), 67-82.
%H Shanzhen Gao and Keh-Hsun Chen, <a href="http://worldcomp-proceedings.com/proc/p2014/FCS2696.pdf">Tackling Sequences From Prudent Self-Avoiding Walks</a>, 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).
%H Emanuele Munarini, <a href="http://www.emis.de/journals/INTEGERS/papers/j29/j29.Abstract.html">Combinatorial properties of the antichains of a garland</a>, Integers, 9 (2009), 353-374.
%H Helmut Prodinger, <a href="https://arxiv.org/abs/2310.12497">Motzkin paths of bounded height with two forbidden contiguous subwords of length two</a>, arXiv:2310.12497 [math.CO], 2023.
%H P. R. Stein and M. S. Waterman, <a href="http://dx.doi.org/10.1016/0012-365X(79)90033-5">On some new sequences generalizing the Catalan and Motzkin numbers</a>, Discrete Math., 26 (1978), 261-272.
%H P. R. Stein and M. S. Waterman, <a href="/A001006/a001006_4.pdf">On some new sequences generalizing the Catalan and Motzkin numbers</a> [Corrected annotated scanned copy]
%H E. J. J. van Rensburg, <a href="http://dx.doi.org/10.1088/0305-4470/38/40/003">Adsorbing bargraph paths in a q-wedge</a>, Journal of Physics A, v.38 n.40, 8505-8525.
%H M. S. Waterman, <a href="http://www.cmb.usc.edu/people/msw/Waterman.html">Home Page</a> (contains copies of his papers)
%H Yan Zhuang, <a href="https://arxiv.org/abs/1508.02793">A generalized Goulden-Jackson cluster method and lattice path enumeration</a>, Discrete Mathematics 341.2 (2018): 358-379; arXiv:1508.02793 [math.CO], 2015-2018.
%F G.f.: 2/(1 - z + z^2 + z^3 + sqrt((1-z^4)(1-2z-z^2))). - _Emeric Deutsch_, Jan 08 2004
%F 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
%F 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
%F a(n) ~ (1+sqrt(2))^(n+1/2)/(sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Aug 10 2013
%F G.f. g(x) satisfies x^2*g^2 - (1-x+x^2+x^3)*g + 1 = 0 and
%F (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
%F 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
%F G.f.: 1/G(x), with G(x)=1-(x-x^3)/(1-x^2/G(x)) (continued fraction). - _Nikolaos Pantelidis_, Jan 11 2023
%e 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 + ...
%p For Maple code producing the g.f. see A004148.
%p # Alternative:
%p 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):
%p map(p, [$0..100]); # _Robert Israel_, May 07 2015
%t a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-2-k ], {k, 2, n-2} ];
%t 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 *)
%o (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 */
%o (Haskell)
%o a004149 n = a004149_list !! n
%o a004149_list = 1 : 1 : 1 : f [1,1,1] where
%o f xs = y : f (y : xs) where
%o y = head xs + sum (zipWith (*) (init $ init $ tail xs) (reverse xs))
%o -- _Reinhard Zumkeller_, Nov 13 2012
%Y Third row of A064645.
%Y Cf. A001006, A004148.
%K nonn,nice
%O 0,5
%A _N. J. A. Sloane_
|
