A202839 Number of stacks of length 1 in all 2ndary structures of size n.
0, 0, 0, 1, 3, 6, 16, 43, 110, 284, 733, 1886, 4853, 12486, 32121, 82647, 212699, 547552, 1410023, 3632260, 9360140, 24129284, 62224692, 160522287, 414246823, 1069376386, 2761502201, 7133442743, 18432633823, 47643696626, 123182434292, 318575889057, 824125660356
Offset: 0
Keywords
Examples
a(5)=6: representing unpaired vertices by v and arcs by AA, BB, etc., the 8 (= A004148(5)) secondary structures of size 5 are vvvvv, AvAvv, vvAvA, AvvAv, vAvvA, AvvvA, vAvAv, ABvBA; they have 0,1,1,1,1,1,1,0 stacks of length 1, respectively.
Links
- I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.
- P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261-272.
Programs
-
Maple
g := z^2*(1-z^2)^2*S*(S-1)/(1-z+z^2-2*z^2*S): S := ((1-z+z^2-sqrt(1-2*z-z^2-2*z^3+z^4))*1/2)/z^2: gser := series(g, z = 0, 35): seq(coeff(gser, z, n), n = 0 .. 32);
-
Mathematica
CoefficientList[Series[-(1 - x^2)^2 * ((1 - x) + (-1 + 2*x + x^3) / Sqrt[(1 - 3*x + x^2) * (1 + x + x^2)]) / (2*x^2), {x, 0, 40}], x] (* Vaclav Kotesovec, May 29 2022 *)
Formula
a(n) = Sum(k*A202838(n,k), k>=0).
a(n) = Sum(k*A202841(n+2,k), k>=0).
a(n) = Sum(k*A202843(n+4,k), k>=0).
G.f.: g(z) = z^2*(1-z^2)^2*S(S - 1)/(1 - z + z^2 -2*z^2*S), where S is defined by S = 1 + z*S + z^2*S(S-1) (the g.f. of the secondary structure numbers A004148).
a(n) ~ 5^(3/4) * phi^(2*n-3) / (2*sqrt(Pi*n)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, May 29 2022
D-finite with recurrence -(n+2)*(406*n-3981)*a(n) +(2022*n^2-15917*n-13552)*a(n-1) +4*(-402*n^2+2594*n+593)*a(n-2) +4*(-605*n^2+7719*n-23415)*a(n-3) +4*(-203*n^2-527*n+15295)*a(n-4) +2*(804*n^2-8404*n+14555)*a(n-5) +(2826*n^2-42913*n+153174)*a(n-6) -(1210*n-6753)*(n-10)*a(n-7)=0. - R. J. Mathar, Jul 26 2022
Comments