The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A110236 Number of (1,0) steps in all peakless Motzkin paths of length n (can be easily translated into RNA secondary structure terminology). 11
 1, 2, 4, 10, 24, 58, 143, 354, 881, 2204, 5534, 13940, 35213, 89162, 226238, 575114, 1464382, 3734150, 9534594, 24374230, 62377881, 159793932, 409717004, 1051405260, 2700168229, 6939388478, 17845927498, 45922416814, 118238842174 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS Number of UHD's in all peakless Motzkin paths of length n+2; here U=(1,1), H=(1,0), and D=(1,-1). Example: a(2)=2 because in HHHH, HUHD, UHDH, and UHHD we have a total of 0+1+1+0 UHD's. LINKS Vincenzo Librandi, Table of n, a(n) for n = 1..200 Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, Grand Dyck paths with air pockets, arXiv:2211.04914 [math.CO], 2022. 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 a(n) = Sum_{k=1..n} k*T(n, k), where T(n, k) = floor(2/(n+k))*binomial((n+k)/2, k)*binomial((n+k)/2, k-1) for n+k mod 2 = 0 and T(n, k)=0 otherwise. G.f.: (1-z+z^2-Q)/(2*z*Q), where Q = sqrt(1 - 2z - z^2 - 2z^3 + z^4). a(n) = Sum_{k=1..n} k*A110235(n,k). a(n) = Sum_{k>=0} k*A190172(n+2,k). a(n+1) = Sum_{k=0..n} Sum_{j=0..n-k} C(k+j,n-k-j)*C(k,n-k-j). - Paul Barry, Oct 24 2006, index corrected Jul 13 2011 a(n+1) = Sum_{k=0..floor(n/2)} C(n-k+1,k+1)*C(n-k,k); a(n+1) := Sum_{k=0..n} C(k+1,n-k+1)*C(k,n-k). - Paul Barry, Aug 17 2009, indices corrected Jul 13 2011 G.f.: z*S^2/(1-z^2*S^2), where S = 1 + z*S + z^2*S*(S-1) (the g.f. of the RNA secondary structure numbers; A004148). a(n) = -f_{n}(-n) with f_1(n)=n and f_{p}(n) = (n+p-1)*(n+p+1-1)^2 *(n+p+2-1)^2*...*(n+p+(p-1)-1)^2/(p!*(p-1)!) + f_{p-1}(n) for p > 1. - Alzhekeyev Ascar M, Jun 27 2011 Let A=floor(n/2), R=n-1, B=A-R/2+1, C=A+1, D=A-R and Z=1 if n mod 2 = 1, otherwise Z = n*(n+2)/4. Then a(n) = Z*Hypergeometric([1,C,C+1,D,D-1],[B,B,B-1/2,B-1/2],1/16). - Peter Luschny, Jan 14 2012 D-finite with recurrence (n+1)*a(n) -3*n*a(n-1) +2*(n-3)*a(n-2) +3*(-n+2)*a(n-3) +2*(n-1)*a(n-4) +3*(-n+4)*a(n-5) +(n-5)*a(n-6)=0. - R. J. Mathar, Nov 30 2012 G.f.: ((1-x+x^2)*((x^2+x+1)*(x^2-3*x+1))^(-1/2)-1)/(2*x). - Mark van Hoeij, Mar 27 2013 From Vaclav Kotesovec, Feb 13 2014: (Start) Recurrence: (n-2)*(n-1)*(n+1)*a(n) = (n-2)*n*(2*n-1)*a(n-1) + (n-1)*(n^2 - 2*n - 2)*a(n-2) + (n-2)*n*(2*n-3)*a(n-3) - (n-3)*(n-1)*n*a(n-4). a(n) ~ (sqrt(5)+3)^(n+1) / (5^(1/4) * sqrt(Pi*n) * 2^(n+2)). (End) EXAMPLE a(3)=4 because in the 2 (=A004148(3)) peakless Motzkin paths of length 3, namely HHH and UHD (where U=(1,1), H=(1,0) and D=(1,-1)), we have altogether 4 H steps. MAPLE T:=proc(n, k) if n+k mod 2 = 0 then 2*binomial((n+k)/2, k)*binomial((n+k)/2, k-1)/(n+k) else 0 fi end:seq(add(k*T(n, k), k=1..n), n=1..33); MATHEMATICA Rest[CoefficientList[Series[((1-x+x^2)*((x^2+x+1)*(x^2-3*x+1))^(-1/2)-1) /(2*x), {x, 0, 20}], x]] (* Vaclav Kotesovec, Feb 13 2014 *) PROG (PARI) x='x+O('x^66); Vec(((1-x+x^2)*((x^2+x+1)*(x^2-3*x+1))^(-1/2)-1)/(2*x)) /* Joerg Arndt, Mar 27 2013 */ CROSSREFS Cf. A004148, A110235, A089732, A190172, A203611, bisection of A202411. Sequence in context: A178036 A191625 A253014 * A191828 A065161 A337317 Adjacent sequences: A110233 A110234 A110235 * A110237 A110238 A110239 KEYWORD nonn AUTHOR Emeric Deutsch, Jul 17 2005 STATUS approved

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.

Last modified December 9 19:36 EST 2022. Contains 358703 sequences. (Running on oeis4.)