A171854 - OEIS

%I #9 Jul 22 2022 12:43:07

%S 0,0,0,1,3,7,19,50,129,334,862,2220,5715,14706,37836,97353,250535,

%T 644905,1660558,4277165,11020698,28406449,73245390,188928736,

%U 487492213,1258305122,3248994414,8391747865,21681628237,56035444491,144864062529

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

%C 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).

%H I. L. Hofacker, P. Schuster and P. F. Stadler, <a href="http://dx.doi.org/10.1016/S0166-218X(98)00073-0">Combinatorics of RNA secondary structures</a>, Discrete Appl. Math., 88, 1998, 207-237.

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

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

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

%e 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).

%p 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);

%Y Cf. A004148, A098093.

%K nonn

%O 0,5

%A _Emeric Deutsch_, Feb 08 2010