A171854 Number of ladders in all peakless Motzkin paths of length n (n>=0).

0, 0, 0, 1, 3, 7, 19, 50, 129, 334, 862, 2220, 5715, 14706, 37836, 97353, 250535, 644905, 1660558, 4277165, 11020698, 28406449, 73245390, 188928736, 487492213, 1258305122, 3248994414, 8391747865, 21681628237, 56035444491, 144864062529

Offset: 0

Author

Emeric Deutsch, Feb 08 2010

Keywords

• nonn

Comments

A string of consecutive up steps U_1, U_2, ..., U_m and their matching down steps D_1, D_2, ..., D_m are said to form a ladder if (i) D_1, D_2, ..., D_m are consecutive steps and (ii) the sequence of pairs (U_j, D_j) (j=1,2,...,m) is maximal. For example, in the path (UU)[U]H[D]H(DD), where U=(1,1), H=(1,0), D=(1,-1), we have 2 ladders, shown between parentheses and square brackets, respectively (can be easily expressed also in RNA secondary structure terminology).

Examples

			a(5)=7 because in the eight (=A004148(5)) peakless Motzkin paths of length 5, i.e. HHHHH, HH(U)H(D), H(U)HH(D), H(U)H(D)H, (U)H(D)HH, (U)HH(D)H, (U)HHH(D) and (UU)H(DD), each path, with the exception of the first, has 1 ladder (shown between parentheses).
		

Links

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

Crossrefs

Cf. A004148, A098093.

Programs

Maple

eq := g = 1+z*g+z^2*g*(g-1): g := RootOf(eq, g): G := z^2*(1-z^2)*g^2*(g-1)/(1-z^2*g^2): Gser := series(G, z = 0, 35): seq(coeff(Gser, z, n), n = 0 .. 32);

Formula

a(n) = Sum_{k>=0} k*A098093(n,k).

G.f. = z^2*(1-z^2)*g^2*(g-1)/(1-z^2*g^2), where g=g(z) is the g.f. of the number of peakless Motzkin paths (A004148), defined by g = 1 + z*g + z^2*g*(g-1). See also eq. (65) in the Hofacker et al. reference.

Conjecture D-finite with recurrence -(n+2)*(1390*n-8929)*a(n) +(4884*n^2-25542*n-20107)*a(n-1) +(60*n^2-6110*n-2249)*a(n-2) +(-5080*n^2+49134*n-115735)*a(n-3) +(-8476*n^2+66210*n-98877)*a(n-4) +(-3652*n^2+41338*n-109281)*a(n-5) +(2878*n-9993)*(n-7)*a(n-6)=0. - R. J. Mathar, Jul 22 2022