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
KEYWORD
nonn
AUTHOR
Aziza Jefferson, Mar 29 2015
STATUS
approved