OFFSET
0,2
COMMENTS
This sequence can also be easily expressed using RNA secondary structure terminology.
LINKS
I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261-272.
M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]
M. S. Waterman, Home Page (contains copies of his papers)
FORMULA
G.f.= g^2/[(1-z)(1-z^2*g^2)], where g=(1-z+z^2-sqrt(1-2z-z^2-2*z^3+z^4))/(2z^2) is the g.f. of sequence A004148 (RNA secondary structures).
a(n) = Sum_{m=0..n+2 }(Sum_{j=1..m/2}(j*Sum_{i=0..m/2-j} ((binomial(2*j+2*i,i)*Sum_{k=0..m-2*j-2*i}(binomial(k,m-k-2*j-2*i)*binomial(k+2*j+2*i-1,k)*(-1)^(k-m)))/(j+i)))). - Vladimir Kruchinin, Mar 07 2016
D-finite with recurrence (n+2)*a(n) +(-4*n-5)*a(n-1) +(5*n-1)*a(n-2) +(-5*n+7)*a(n-3) +(5*n-3)*a(n-4) +(-5*n+9)*a(n-5) +(4*n-13)*a(n-6) +(-n+4)*a(n-7)=0. - R. J. Mathar, Jul 24 2022
EXAMPLE
a(1)=3 because in the four peakless Motzkin paths of length 4, namely HHHH, H(UHD), (UHD)H and (UHHD), we have altogether three subwords of the required form (shown between parentheses).
PROG
(Maxima)
a(n):=sum(sum(j*sum((binomial(2*j+2*i, i)*sum(binomial(k, m-k-2*j-2*i)*binomial(k+2*j+2*i-1, k)*(-1)^(k-m), k, 0, m-2*j-2*i))/(j+i), i, 0, m/2-j), j, 1, m/2), m, 0, n+2); /* Vladimir Kruchinin, Mar 07 2016 */
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jan 08 2004
STATUS
approved