|
%I #55 Nov 14 2022 20:01:33
%S 1,2,4,10,24,58,143,354,881,2204,5534,13940,35213,89162,226238,575114,
%T 1464382,3734150,9534594,24374230,62377881,159793932,409717004,
%U 1051405260,2700168229,6939388478,17845927498,45922416814,118238842174
%N Number of (1,0) steps in all peakless Motzkin paths of length n (can be easily translated into RNA secondary structure terminology).
%C 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.
%H Vincenzo Librandi, <a href="/A110236/b110236.txt">Table of n, a(n) for n = 1..200</a>
%H Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, <a href="https://arxiv.org/abs/2211.04914">Grand Dyck paths with air pockets</a>, arXiv:2211.04914 [math.CO], 2022.
%H W. R. Schmitt and M. S. Waterman, <a href="http://dx.doi.org/10.1016/0166-218X(92)00038-N">Linear trees and RNA secondary structure</a>, Discrete Appl. Math., 51, 317-323, 1994.
%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 (1978), 261-272.
%H M. Vauchassade de Chaumont and G. Viennot, <a href="https://www.emis.de/journals/SLC/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire</a>, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.
%F 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.
%F G.f.: (1-z+z^2-Q)/(2*z*Q), where Q = sqrt(1 - 2z - z^2 - 2z^3 + z^4).
%F a(n) = Sum_{k=1..n} k*A110235(n,k).
%F a(n) = Sum_{k>=0} k*A190172(n+2,k).
%F 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
%F 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
%F 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).
%F 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
%F 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
%F 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
%F 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
%F From _Vaclav Kotesovec_, Feb 13 2014: (Start)
%F 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).
%F a(n) ~ (sqrt(5)+3)^(n+1) / (5^(1/4) * sqrt(Pi*n) * 2^(n+2)). (End)
%e 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.
%p 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);
%t 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 *)
%o (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 */
%Y Cf. A004148, A110235, A089732, A190172, A203611, bisection of A202411.
%K nonn
%O 1,2
%A _Emeric Deutsch_, Jul 17 2005
|
