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,2

Comments

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

Row sums of A110238.

Links

Table of n, a(n) for n=3..30.

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.

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

Example

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.

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

Crossrefs

Cf. A004148, A110238.

Sequence in context: A374773 A020962 A027243 * A271893 A001853 A217898

Adjacent sequences: A110236 A110237 A110238 * A110240 A110241 A110242

Keyword

nonn

Author

Emeric Deutsch, Jul 17 2005

Status

approved