login
This site is supported by donations to The OEIS Foundation.

 

Logo


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)
13

%I M1131

%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 T. D. Noe and 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 M. Bernstein and N. J. A. Sloane, <a href="http://arXiv.org/abs/math.CO/0205301">Some canonical sequences of integers</a>, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]

%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, 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 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 Zhuang, Yan. <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. Also arXiv: 1508.02793v2.

%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 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

%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,changed

%O 0,5

%A _N. J. A. Sloane_

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

License Agreements, Terms of Use, Privacy Policy .

Last modified February 23 00:03 EST 2018. Contains 299472 sequences. (Running on oeis4.)