OFFSET
3,2
COMMENTS
Sequence name can be easily translated into RNA secondary structure terminology.
Row sums of A110238.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 3..2397
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
a(n) = Sum_{k>=0} k * A089732(n,k). - Alois P. Heinz, Apr 12 2026
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);
# Alternative:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
`if`(x=0, [1, 0], (p-> p+[0, p[1]])(b(x-1, y+1, true))+
`if`(t, 0, b(x-1, y-1, false))+b(x-1, y, false)))
end:
a:= n-> b(n, 0, false)[2]:
seq(a(n), n=3..32); # Alois P. Heinz, Apr 13 2026
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jul 17 2005
STATUS
approved