login
A171854
Number of ladders in all peakless Motzkin paths of length n (n>=0).
1
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,5
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).
LINKS
I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.
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
EXAMPLE
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).
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);
CROSSREFS
Sequence in context: A298416 A151266 A147234 * A182895 A087224 A308398
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Feb 08 2010
STATUS
approved