OFFSET
0,3
LINKS
Aziza Jefferson, The Substitution Decomposition of Matchings and RNA Secondary Structures, PhD Thesis, University of Florida, 2015.
FORMULA
a(n) = Sum_{i=0..n-2} C_i*(Sum_{j=1..n-i} C_j - (n-i)) + C_n where C is A000108.
From Vaclav Kotesovec, Jul 13 2017: (Start)
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).
a(n) ~ 41 * 4^n / (9*sqrt(Pi)*n^(3/2)).
(End)
MAPLE
a:= proc(n) option remember; `if`(n<4, [1$2, 3, 11][n+1],
(2*(74*n^2-69*n-110)*a(n-1)-3*(89*n^2-139*n-70)*a(n-2)+
2*(91*n^2-204*n-52)*a(n-3)-4*(5*n+1)*(2*n-7)*a(n-4))
/((n+2)*(23*n-43)))
end:
seq(a(n), n=0..40); # Alois P. Heinz, Jul 13 2017
MATHEMATICA
c[n_] := c[n] = CatalanNumber[n];
b[n_] := b[n] = If[n<2, 0, 2+((5n-9) b[n-1] - (4n-2) b[n-2])/(n-1)];
a[n_] := Sum[c[i] Sum[c[j]-(n-i), {j, 1, n-i}], {i, 0, n-2}] + b[n] + c[n];
a /@ Range[0, 40] (* Jean-François Alcover, Nov 29 2020 *)
PROG
(Python)
from functools import cache
@cache
def a(n):
return (
[1, 1, 3, 11][n]
if n < 4
else (
2 * (74 * n ** 2 - 69 * n - 110) * a(n - 1)
- 3 * (89 * n ** 2 - 139 * n - 70) * a(n - 2)
+ 2 * (91 * n ** 2 - 204 * n - 52) * a(n - 3)
- 4 * (5 * n + 1) * (2 * n - 7) * a(n - 4)
)
// ((n + 2) * (23 * n - 43))
)
print([a(n) for n in range(27)])
# Indranil Ghosh, Jul 15 2017, after Maple code, updated by Peter Luschny, Nov 29 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
Kyle Goryl, Jul 13 2017
EXTENSIONS
More terms from Alois P. Heinz, Jul 13 2017
STATUS
approved