A202846 Number of stacks of odd length in all 2ndary structures of size n.
0, 0, 0, 1, 3, 6, 16, 44, 113, 290, 749, 1930, 4966, 12776, 32870, 84577, 217665, 560328, 1442893, 3716837, 9577805, 24689612, 63667585, 164239124, 423824628, 1094065998, 2825169786, 7297681867, 18856458451, 48737762624, 126007604078, 325873570924, 842982118807
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 odd length, 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)*S*(S-1)/((1+z^2)*(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);
Formula
a(n) = Sum(k*A202845(n,k), k>=0).
a(n) = Sum(k*A202848(n+2,k), k>=0).
a(n)+a(n-2) = A171854(n) (n>=2).
G.f.: g(z) = z^2*(1-z^2)^2*S(S - 1)/[(1+z^2)(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).
Conjecture D-finite with recurrence +(n+2)*(13230*n^2-96611*n+147133)*a(n) +(-44206*n^3+292903*n^2-261197*n-341332)*a(n-1) +2*(17746*n^3-141629*n^2+231187*n+123600)*a(n-2) +2*(-26460*n^3+157889*n^2-64195*n-381418)*a(n-3) +2*(35492*n^3-320849*n^2+745453*n-240088)*a(n-4) +2*(-13230*n^3+98869*n^2-160610*n-79637)*a(n-5) +(48722*n^3-428591*n^2+982443*n-433110)*a(n-6) -(n-6)*(17746*n^2-68387*n+43705)*a(n-7)=0. - R. J. Mathar, Jul 26 2022
Comments