A110239 Number of (1,1) steps in all peakless Motzkin paths of length n.
1, 3, 8, 22, 58, 151, 392, 1013, 2612, 6728, 17318, 44564, 114671, 295099, 759576, 1955657, 5036741, 12976355, 33443190, 86221745, 222371926, 573713958, 1480677048, 3822708372, 9872424913, 25504336609, 65907869404, 170368399138
Offset: 3
Keywords
Examples
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.
Links
- W. R. Schmitt and M. S. Waterman, Linear trees and RNA secondary structure, Discrete Appl. Math., 51, 317-323, 1994.
- P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.
- M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.
Programs
-
Maple
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);
Formula
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).
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
Comments