login
Number of R&E Family matchings on n edges.
1

%I #13 Oct 06 2019 09:04:45

%S 1,3,14,84,592,4624,38527,334520,2985938,27183525,251204717,

%T 2349231434,22186989871,211295835831,2026765351330,19563183525857,

%U 189878734136185,1852021863338181,18143610295356357,178450501118284066,1761425423533593329,17443012946883397306,173247241040324621443,1725404763442479917997,17226646104539624029186,172389875494663129310211,1728819399958251503320772,17371923980126335814068340,174882805619639894274925366,1763573883561574064590764255,17813088298000097109198747848,180193867968101208748329431620,1825392351254024651444300421782,18516189068195200519689971895953,188058513067187124022632768762920,1912273561123769149363329826421051,19466808894886697821847017471202077,198381665775949932177580813656191187,2023702201274806730119560173885757279,20663697938590662344370538856632433182

%N Number of R&E Family matchings on n edges.

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

%H A. Condon, B. Davy, B. Rastegari, S. Zhao and F. Tarrant, <a href="http://dx.doi.org/10.1016/j.tcs.2004.03.042"> RNA pseudoknotted structures</a>, Theoret. Comput. Sci. 320(1), (2004), 35-50.

%H Aziza Jefferson, <a href="http://ufdc.ufl.edu/UFE0047620">The Substitution Decomposition of Matchings and RNA Secondary Structures</a>, PhD Thesis, University of Florida, 2015.

%H E. Rivas and S.R. Eddy, <a href="http://dx.doi.org/10.1006/jmbi.1998.2436">A dynamic programing algorithm for RNA structure prediction including pseudoknots</a>, J. Mol. Biol., 285, (1999), 2053-2068.

%F 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.

%e 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.

%p 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);

%Y Cf. A256330, A256338

%K nonn

%O 1,2

%A _Aziza Jefferson_, Mar 29 2015