A256338 Number of A&U Family matchings on n edges.
1, 3, 14, 81, 526, 3655, 26522, 198322, 1516296, 11794717, 93028387, 742192059, 5978650560, 48558821234, 397218622275, 3269629207524, 27061726430000, 225078993453143, 1880240716499975, 15768890757767329, 132719696885282352, 1120664726059889642, 9490737694928103944, 80593740187789336604, 686097231181385302494, 5854230604182513256777, 50058728487687099021228, 428893610758038945556024, 3681458291424994103104272, 31654643493605098603330050, 272617697673293256259943417, 2351397730980411031399548438, 20310185543805378949877753778, 175663385844074502933143530174, 1521230708939544454165789841800, 13189400713003422051741601456307, 114483609078595784724427186310842, 994773380472692869438699360298740, 8652545469871591210786412806190538
Offset: 1
Keywords
Examples
a(4)=81 because of the 105 matchings on 4 edges which can be drawn in the plane, 24 do not lie in the A&U Family. Of these 24, only three lie in the R&E family. In canonical sequence form the three missing matchings are given by 12134324, 12324314, and 12343142.
Links
- T. Akutsu, Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots, Discrete Appl. Math. 104(1-2), (2000), 45-62.
- A. Condon, B. Davy, B. Rastegari, S. Zhao and F. Tarrant, RNA pseudoknotted structures, Theoret. Comput. Sci. 320(1), (2004), 35-50.
- Aziza Jefferson, The Substitution Decomposition of Matchings and RNA Secondary Structures, PhD Thesis, University of Florida, 2015.
- C. Saule, M. Régnier, J.-M. Steyaert, and A. Denise, Counting RNA pseudoknotted structures, J. Comput. Biol. 18(10), (2011), 1339-1351.
- Y. Uemura, A. Hasegawa, S. Kobayashi, and T. Yokomori, Tree adjoining grammars for RNA structure prediction, Theoret. Comput. Sci. 210(2), (1999), 277-303.
Programs
-
Maple
f := RootOf(2*x^7*_Z^(14)-2*x^6*_Z^(13)-3*x^6*_Z^(12)+7*x^5*_Z^(11)+3*x^5*_Z^(10)-16*x^4*_Z^9+2*x^4*_Z^8+18*x^3*_Z^7-7*x^2*_Z^5+(-12*x^3+2*x^2)*_Z^6+(4*x^2-5*x)*_Z^4+10*x*_Z^3+(-5*x+1)*_Z^2-2*_Z+1); convert(series(f, x=0, 40), radical);
Formula
G.f. f satisfies 2x^7f^14 - 2x^6f^13 - 3x^6f^12 + 7x^5f^11 + 3x^5f^10 - 16x^4f^9 + 2x^4f^8 + 18x^3f^7 - 7x^2f^5 + (-12x^3 + 2x^2)f^6 + (4x^2 - 5x)f^4 + 10xf^3 + (-5x+1)f^2 - 2f + 1 = 0.
Comments