login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A089742 Number of subwords UHH...HD in all peakless Motzkin paths of length n+3, where U=(1,1), D=(1,-1) and H=(1,0). 0
1, 3, 7, 17, 41, 99, 242, 596, 1477, 3681, 9215, 23155, 58368, 147530, 373768, 948882, 2413264, 6147414, 15682008, 40056238, 102434119, 262228051, 671945055, 1723350315, 4423518544, 11362907022, 29208834520, 75131251334, 193370093508 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

This sequence can also be easily expressed using RNA secondary structure terminology.

LINKS

Table of n, a(n) for n=0..28.

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

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

Cf. A004148.

Sequence in context: A001333 A123335 A078057 * A187258 A131721 A259855

Adjacent sequences:  A089739 A089740 A089741 * A089743 A089744 A089745

KEYWORD

nonn

AUTHOR

Emeric Deutsch, Jan 08 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 05:23 EDT 2018. Contains 316275 sequences. (Running on oeis4.)