A256337 Number of R&E Family matchings on n edges.

1, 3, 14, 84, 592, 4624, 38527, 334520, 2985938, 27183525, 251204717, 2349231434, 22186989871, 211295835831, 2026765351330, 19563183525857, 189878734136185, 1852021863338181, 18143610295356357, 178450501118284066, 1761425423533593329, 17443012946883397306, 173247241040324621443, 1725404763442479917997, 17226646104539624029186, 172389875494663129310211, 1728819399958251503320772, 17371923980126335814068340, 174882805619639894274925366, 1763573883561574064590764255, 17813088298000097109198747848, 180193867968101208748329431620, 1825392351254024651444300421782, 18516189068195200519689971895953, 188058513067187124022632768762920, 1912273561123769149363329826421051, 19466808894886697821847017471202077, 198381665775949932177580813656191187, 2023702201274806730119560173885757279, 20663697938590662344370538856632433182

Offset

1,2

Comments

The R&E Family of matchings is the largest family of matchings formed by repeated edge pinnings, edge inflations by ladders and vertex insertions.

Links

Table of n, a(n) for n=1..40.

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.

E. Rivas and S.R. Eddy, A dynamic programing algorithm for RNA structure prediction including pseudoknots, J. Mol. Biol., 285, (1999), 2053-2068.

Formula

G.f. f satisfies 2*x^(30)*f^(60) - 2*x^(29)*f^(59) - 38*x^(29)*f^(58) + 43*x^(28)*f^(57) + 342*x^(28)*f^(56) - 452*x^(27)*f^(55) - 1952*x^(27)*f^(54) + 3104*x^(26)*f^(53) + 8030*x^(26)*f^(52) - 15740*x^(25)*f^(51) - 25796*x^(25)*f^(50) + 63234*x^(24)*f^(49) + 68385*x^(24)*f^(48) - 210718*x^(23)*f^(47) - 154085*x^(23)*f^(46) + 600645*x^(22)*f^(45) + 295081*x^(22)*f^(44) - 1493939*x^(21)*f^(43) - (465768*x^(21)-30*x^(20))*f^(42) + 3281450*x^(20)*f^(41) + (556761*x^(20)-535*x^(19))*f^(40) - 6407159*x^(19)*f^(39) - (345063*x^(19)-4503*x^(18))*f^(38) + 11148795*x^(18)*f^(37) - (486467*x^(18)+23656*x^(17))*f^(36) - 17269156*x^(17)*f^(35) + (2247622*x^(17)+86500*x^(16))*f^(34) + 23701163*x^(16)*f^(33) - (5008690*x^(16)+232556*x^(15))*f^(32) - (28606954*x^(15)-2*x^(14))*f^(31) + (8286505*x^(15)+473426*x^(14))*f^(30) + (30112233*x^(14)-33*x^(13))*f^(29) - (10981985*x^(14)+739870*x^(13))*f^(28) - (27473085*x^(13)-241*x^(12))*f^(27) + (11935909*x^(13)+887762*x^(12))*f^(26) + (21720351*x^(12)-1046*x^(11))*f^(25) - (10798494*x^(12)+802751*x^(11))*f^(24) - (15014115*x^(11)-3036*x^(10))*f^(23) + (8290091*x^(11)+514052*x^(10))*f^(22) + (9236626*x^(10)-6259*x^(9))*f^(21) - (5538246*x^(10)+180970*x^(9))*f^(20) - (5149642*x^(9)-9471*x^(8))*f^(19) + (3290018*x^(9)-42243*x^(8))*f^(18) + (2610905*x^(8)-10692*x^(7))*f^(17) - (1741070*x^(8)-114094*x^(7))*f^(16) - (1180928*x^(7)-9042*x^(6))*f^(15) + (800928*x^(7)-91214*x^(6))*f^(14) + (460434*x^(6)-5687*x^(5))*f^(13) - (307889*x^(6)-46482*x^(5))*f^(12) - (148829*x^(5)-2607*x^(4))*f^(11) + (94979*x^(5)-16566*x^(4))*f^(10) + (38177*x^(4)-838*x^(3))*f^(9) - (22576*x^(4)-4140*x^(3))*f^(8) - (7344*x^(3)-176*x^(2))*f^(7) + (3919*x^(3)-695*x^(2))*f^(6) + (981*x^(2)-21*x)*f^(5) - (458*x^(2)-70*x)*f^(4) - (81*x-1)*f^(3) + (32*x-3)*f^(2) + 3*f - 1 = 0.

Example

a(6)=4624 because, of the 4659 matchings on 6 edges which can be drawn in the plane, 65 do not lie in the R&E Family. In canonical sequence form, two of these missing matchings are given by 123143546526 and 123145643625.

Maple

f := RootOf(2*x^(30)*_Z^(60) - 2*x^(29)*_Z^(59) - 38*x^(29)*_Z^(58) + 43*x^(28)*_Z^(57) + 342*x^(28)*_Z^(56) - 452*x^(27)*_Z^(55) - 1952*x^(27)*_Z^(54) + 3104*x^(26)*_Z^(53) + 8030*x^(26)*_Z^(52) - 15740*x^(25)*_Z^(51) - 25796*x^(25)*_Z^(50) + 63234*x^(24)*_Z^(49) + 68385*x^(24)*_Z^(48) - 210718*x^(23)*_Z^(47) - 154085*x^(23)*_Z^(46) + 600645*x^(22)*_Z^(45) + 295081*x^(22)*_Z^(44) - 1493939*x^(21)*_Z^(43) - (465768*x^(21)-30*x^(20))*_Z^(42) + 3281450*x^(20)*_Z^(41) + (556761*x^(20)-535*x^(19))*_Z^(40) - 6407159*x^(19)*_Z^(39) - (345063*x^(19)-4503*x^(18))*_Z^(38) + 11148795*x^(18)*_Z^(37) - (486467*x^(18)+23656*x^(17))*_Z^(36) - 17269156*x^(17)*_Z^(35) + (2247622*x^(17)+86500*x^(16))*_Z^(34) + 23701163*x^(16)*_Z^(33) - (5008690*x^(16)+232556*x^(15))*_Z^(32) - (28606954*x^(15)-2*x^(14))*_Z^(31) + (8286505*x^(15)+473426*x^(14))*_Z^(30) + (30112233*x^(14)-33*x^(13))*_Z^(29) - (10981985*x^(14)+739870*x^(13))*_Z^(28) - (27473085*x^(13)-241*x^(12))*_Z^(27) + (11935909*x^(13)+887762*x^(12))*_Z^(26) + (21720351*x^(12)-1046*x^(11))*_Z^(25) - (10798494*x^(12)+802751*x^(11))*_Z^(24) - (15014115*x^(11)-3036*x^(10))*_Z^(23) + (8290091*x^(11)+514052*x^(10))*_Z^(22) + (9236626*x^(10)-6259*x^(9))*_Z^(21) - (5538246*x^(10)+180970*x^(9))*_Z^(20) - (5149642*x^(9)-9471*x^(8))*_Z^(19) + (3290018*x^(9)-42243*x^(8))*_Z^(18) + (2610905*x^(8)-10692*x^(7))*_Z^(17) - (1741070*x^(8)-114094*x^(7))*_Z^(16) - (1180928*x^(7)-9042*x^(6))*_Z^(15) + (800928*x^(7)-91214*x^(6))*_Z^(14) + (460434*x^(6)-5687*x^(5))*_Z^(13) - (307889*x^(6)-46482*x^(5))*_Z^(12) - (148829*x^(5)-2607*x^(4))*_Z^(11) + (94979*x^(5)-16566*x^(4))*_Z^(10) + (38177*x^(4)-838*x^(3))*_Z^(9) - (22576*x^(4)-4140*x^(3))*_Z^(8) - (7344*x^(3)-176*x^(2))*_Z^(7) + (3919*x^(3)-695*x^(2))*_Z^(6) + (981*x^(2)-21*x)*_Z^(5) - (458*x^(2)-70*x)*_Z^(4) - (81*x-1)*_Z^(3) + (32*x-3)*_Z^(2) + 3*_Z - 1, 1); series(f, x=0, 40);

Crossrefs

Cf. A256330, A256338

Sequence in context: A352307 A359335 A074535 * A256330 A190761 A005700

Adjacent sequences: A256334 A256335 A256336 * A256338 A256339 A256340

Keyword

nonn

Author

Aziza Jefferson, Mar 29 2015

Status

approved