login
The OEIS is supported by the many generous donors 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). 1

%I #20 Jul 24 2022 11:57:42

%S 1,3,7,17,41,99,242,596,1477,3681,9215,23155,58368,147530,373768,

%T 948882,2413264,6147414,15682008,40056238,102434119,262228051,

%U 671945055,1723350315,4423518544,11362907022,29208834520,75131251334,193370093508

%N 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).

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

%H I. L. Hofacker, P. Schuster and P. F. Stadler, <a href="http://dx.doi.org/10.1016/S0166-218X(98)00073-0">Combinatorics of RNA secondary structures</a>, Discrete Appl. Math., 88, 1998, 207-237.

%H P. R. Stein and M. S. Waterman, <a href="http://dx.doi.org/10.1016/0012-365X(79)90033-5">On some new sequences generalizing the Catalan and Motzkin numbers</a>, Discrete Math., 26 (1979), 261-272.

%H M. Vauchassade de Chaumont and G. Viennot, <a href="http://www.mat.univie.ac.at/~slc/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire</a>, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]

%H M. S. Waterman, <a href="http://www.cmb.usc.edu/people/msw/Waterman.html">Home Page</a> (contains copies of his papers)

%F 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).

%F 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

%F 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

%e 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).

%o (Maxima)

%o 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 */

%Y Cf. A004148.

%Y Partial sums of A110236.

%K nonn

%O 0,2

%A _Emeric Deutsch_, Jan 08 2004

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 01:36 EDT 2024. Contains 371264 sequences. (Running on oeis4.)