login
Number of (1,1) steps in all peakless Motzkin paths of length n.
1

%I #12 Jul 24 2022 11:12:35

%S 1,3,8,22,58,151,392,1013,2612,6728,17318,44564,114671,295099,759576,

%T 1955657,5036741,12976355,33443190,86221745,222371926,573713958,

%U 1480677048,3822708372,9872424913,25504336609,65907869404,170368399138

%N Number of (1,1) steps in all peakless Motzkin paths of length n.

%C Sequence name can be easily translated into RNA secondary structure terminology.

%C Row sums of A110238.

%H W. R. Schmitt and M. S. Waterman, <a href="http://dx.doi.org/10.1016/0166-218X(92)00038-N">Linear trees and RNA secondary structure</a>, Discrete Appl. Math., 51, 317-323, 1994.

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

%H M. Vauchassade de Chaumont and G. Viennot, <a href="https://www.emis.de/journals/SLC/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire</a>, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.

%F G.f.: z^2g^2*(g-1)/(1-z^2*g^2), where g=1+zg+z^2*g(g-1)=[1-z+z^2-sqrt(1-2z-z^2-2z^3+z^4)]/(2z^2) is the g.f. of the RNA secondary structure numbers (A004148).

%F D-finite with recurrence -(n+2)*(26*n-99)*a(n) +(126*n^2-385*n-386)*a(n-1) +(-122*n^2+531*n-386)*a(n-2) +(-22*n^2+167*n-122)*a(n-3) +(-174*n^2+851*n-882)*a(n-4) +(74*n-117)*(n-4)*a(n-5)=0. - _R. J. Mathar_, Jul 24 2022

%e a(5)=8 because in the 8 (=A004148(5)) peakless Motzkin paths of length 5, namely HHHHH, UHDHH, UHHDH, UHHHD, HUHDH, HUHHD, HHUHD and UUHDD (where U=(1,1), H=(1,0) and D=(1,-1)), we have altogether 8 U steps.

%p g:=(1-z+z^2-sqrt(1-2*z-z^2-2*z^3+z^4))/2/z^2: G:=z^2*g^2*(g-1)/(1-z^2*g^2): Gser:=series(G,z=0,37): seq(coeff(Gser,z^n),n=3..34);

%Y Cf. A004148, A110238.

%K nonn

%O 3,2

%A _Emeric Deutsch_, Jul 17 2005