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

M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.

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)

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

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} ];

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 A110334 A084636

Adjacent sequences:  A004146 A004147 A004148 * A004150 A004151 A004152

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 27 12:14 EDT 2017. Contains 284176 sequences.