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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

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). 10
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.

a(n)=sum(k*A110235(n,k),k=1..n).

a(n)=sum(k*A190172(n+2,k),k>=0).

REFERENCES

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, 1979, 261-272.

M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux et problemes d'enumeration en biologie moleculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 1..200

FORMULA

a(n)=sum(k*T(n, k), k=1..n), where T(n, k)=[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)/(2zQ), where Q=sqrt(1-2z-z^2-2z^3+z^4).

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)}. [From Paul Barry, Aug 17 2009, indices corrected Jul 13 2011]

G.f. = z*S^2/(1-z^2*S^2), where S=1+zS+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

Conjecture: (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

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). - Vaclav Kotesovec, Feb 13 2014

a(n) ~ (sqrt(5)+3)^(n+1) / (5^(1/4) * sqrt(Pi*n) * 2^(n+2)). - Vaclav Kotesovec, Feb 13 2014

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: A163271 A178036 A191625 * A191828 A065161 A191758

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 23 19:18 EDT 2014. Contains 240946 sequences.