cp's OEIS Frontend

A289834 Number of perfect matchings on n edges which represent RNA secondary folding structures characterized by the Lyngso and Pedersen (L&P) family and the Cao and Chen (C&C) family.

%I A289834 #36 Mar 06 2022 10:30:40
%S A289834 1,1,3,11,39,134,456,1557,5364,18674,65680,233182,834796,3010712,
%T A289834 10929245,39904623,146451871,539972534,1999185777,7429623640,
%U A289834 27705320423,103636336176,388775988319,1462261313876,5513152229901,20832701135628,78884459229627
%N A289834 Number of perfect matchings on n edges which represent RNA secondary folding structures characterized by the Lyngso and Pedersen (L&P) family and the Cao and Chen (C&C) family.
%H A289834 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.
%F A289834 a(n) = Sum_{i=0..n-2} C_i*(Sum_{j=1..n-i} C_j - (n-i)) + C_n where C is A000108.
%F A289834 From _Vaclav Kotesovec_, Jul 13 2017: (Start)
%F A289834 D-finite recurrence (of order 3): (n+2)*(41*n^3 - 228*n^2 + 391*n - 180)*a(n) = 6*(41*n^4 - 187*n^3 + 192*n^2 + 120*n - 160)*a(n-1) - 3*(3*n - 4)*(41*n^3 - 146*n^2 + 83*n + 70)*a(n-2) + 2*(2*n - 5)*(41*n^3 - 105*n^2 + 58*n + 24)*a(n-3).
%F A289834 a(n) ~ 41 * 4^n / (9*sqrt(Pi)*n^(3/2)).
%F A289834 (End)
%p A289834 a:= proc(n) option remember; `if`(n<4, [1$2, 3, 11][n+1],
%p A289834       (2*(74*n^2-69*n-110)*a(n-1)-3*(89*n^2-139*n-70)*a(n-2)+
%p A289834        2*(91*n^2-204*n-52)*a(n-3)-4*(5*n+1)*(2*n-7)*a(n-4))
%p A289834        /((n+2)*(23*n-43)))
%p A289834     end:
%p A289834 seq(a(n), n=0..40);  # _Alois P. Heinz_, Jul 13 2017
%t A289834 c[n_] := c[n] = CatalanNumber[n];
%t A289834 b[n_] := b[n] = If[n<2, 0, 2+((5n-9) b[n-1] - (4n-2) b[n-2])/(n-1)];
%t A289834 a[n_] := Sum[c[i] Sum[c[j]-(n-i), {j, 1, n-i}], {i, 0, n-2}] + b[n] + c[n];
%t A289834 a /@ Range[0, 40] (* _Jean-François Alcover_, Nov 29 2020 *)
%o A289834 (Python)
%o A289834 from functools import cache
%o A289834 @cache
%o A289834 def a(n):
%o A289834     return (
%o A289834         [1, 1, 3, 11][n]
%o A289834         if n < 4
%o A289834         else (
%o A289834               2 * (74 * n ** 2 - 69 * n - 110) * a(n - 1)
%o A289834             - 3 * (89 * n ** 2 - 139 * n - 70) * a(n - 2)
%o A289834             + 2 * (91 * n ** 2 - 204 * n - 52) * a(n - 3)
%o A289834             - 4 * (5 * n + 1) * (2 * n - 7) * a(n - 4)
%o A289834         )
%o A289834         // ((n + 2) * (23 * n - 43))
%o A289834     )
%o A289834 print([a(n) for n in range(27)])
%o A289834 # _Indranil Ghosh_, Jul 15 2017, after Maple code, updated by _Peter Luschny_, Nov 29 2020
%Y A289834 Cf. A000108, A256334.
%K A289834 nonn
%O A289834 0,3
%A A289834 _Kyle Goryl_, Jul 13 2017
%E A289834 More terms from _Alois P. Heinz_, Jul 13 2017