A114713 Number of ascents in all peakless Motzkin paths of length n+3.

1, 3, 7, 18, 46, 116, 294, 746, 1894, 4816, 12262, 31258, 79777, 203833, 521337, 1334690, 3420039, 8770891, 22510949, 57817420, 148599626, 382165858, 983430962, 2532082308, 6522876601, 16811813391, 43350264107, 111830286218

Offset

0,2

Comments

A Motzkin path of length n is a lattice path from (0,0) to (n,0) consisting of U=(1,1), D=(1,-1) and H=(1,0) steps and never going below the x-axis. An ascent in a Motzkin path is a maximal sequence of consecutive U steps.

Links

Table of n, a(n) for n=0..27.

I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.

P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261-272.

M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Sem. Loth. Comb. B08l (1984) 79-86.

Formula

a(n) = Sum(k*A114712(n+3,k),k=0..1+floor(n/3)).

G.f.: (1-2z+z^2-2z^3+z^4-(1-z+z^2)sqrt(1-2z-z^2-2z^3+z^4))/(2z^4*sqrt(1-2z-z^2-2z^3+z^4)).

D-finite with recurrence n^2*(n+4)*a(n) -n*(n+2)*(2*n+3)*a(n-1) -(n+4)*(n-2)*(n+1)*a(n-2) -n*(n+2)*(2*n+1)*a(n-3) +(n-2)*(n+2)^2*a(n-4)=0. - R. J. Mathar, Jul 24 2022

Example

a(2)=7 because in the 8 (=A004148(5)) peakless Motzkin paths of length 5, namely HHHHH, (U)HDHH, (U)HHDH, (U)HHHD, H(U)HDH, H(U)HHD, HH(U)HD and (UU)HDD, we have altogether 7 ascents (shown between parentheses).

Maple

G:=(1-2*z+z^2-2*z^3+z^4-(1-z+z^2)*sqrt(1-2*z-z^2-2*z^3+z^4))/2/z^4/(1-2*z-z^2-2*z^3+z^4)^(1/2): Gser:=series(G, z=0, 40): 1, seq(coeff(Gser, z^n), n=1..32);

Crossrefs

Cf. A004148, A114712.

Sequence in context: A191652 A191826 A318899 * A078058 A116413 A052960

Adjacent sequences: A114710 A114711 A114712 * A114714 A114715 A114716

Keyword

nonn

Author

Emeric Deutsch, Dec 27 2005

Status

approved