%I #23 Jul 24 2022 12:07:54

%S 1,3,7,17,41,98,235,565,1362,3294,7992,19450,47475,116204,285178,

%T 701585,1730003,4275162,10586164,26263365,65273566,162499838,

%U 405185762,1011815774,2530219435,6335642377,15884284791,39871297479,100194076029

%N Number of (1,1) steps starting at level zero in all peakless Motzkin paths of length n+3.

%C This sequence can be easily expressed also in RNA secondary structure terminology.

%C Lim_{n->infinity} a(n)/A004148(n) = sqrt(5).

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

%H P. R. Stein and M. S. Waterman, <a href="https://doi.org/10.1016/0012-365X(79)90033-5">On some new sequences generalizing the Catalan and Motzkin numbers</a>, Discrete Math., 26 (1979), 261-272.

%H M. Vauchassade de Chaumont and G. Viennot, <a href="http://www.mat.univie.ac.at/~slc/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumeration en biologie moléculaire</a>, Sem. Loth. Comb. B08l (1984) 79-86.

%H M. S. Waterman, <a href="http://www.cmb.usc.edu/people/msw/Waterman.html">Home Page</a> (contains copies of his papers)

%F a(n) = Sum_{k=ceiling(n/2+1)..n+1} (5k-2n-2)*binomial(k,n+1-k) * binomial(k+1,n+3-k)/(k*(n+4-k)).

%F a(n) = A004148(n+5) - 2*A004148(n+4) + A004148(n+3) - A004148(n+2).

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

%F D-finite with recurrence -(n+7)*(86*n-51)*a(n) +3*(95*n^2+434*n-249)*a(n-1) +4*(-35*n^2-71*n-60)*a(n-2) +(59*n^2+209*n+1020)*a(n-3) +6*(-52*n^2+11*n+71)*a(n-4) +(113*n+119)*(n-3)*a(n-5)=0. - _R. J. Mathar_, Jul 24 2022

%e a(2)=7 because in the eight peakless Motzkin paths of length 5, namely HHHHH, HHU'HD, HU'HHD, HU'HDH, U'HDHH, U'HHDH, U'HHHD and U'UHDD, where U=(1,1), D=(1,-1), H=(1,0), we have altogether seven U steps starting at level zero (indicated by U').

%Y Cf. A004148.

%K nonn

%O 0,2

%A _Emeric Deutsch_, Jan 07 2004