A110236 Number of (1,0) steps in all peakless Motzkin paths of length n (can be easily translated into RNA secondary structure terminology).
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
Offset: 1
Keywords
Examples
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.
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.
Programs
-
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 *) -
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 */
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)
Comments