login
A256338
Number of A&U Family matchings on n edges.
1
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,2
COMMENTS
The A&U Family of matchings is the largest family of matchings formed by pinning edges to the right, edge inflation by ladders and vertex insertions.
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.
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.
EXAMPLE
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.
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);
CROSSREFS
Sequence in context: A354325 A346966 A256336 * A256331 A292875 A077054
KEYWORD
nonn
AUTHOR
Aziza Jefferson, Mar 29 2015
STATUS
approved