A190170 -id:A190170 - cp's OEIS frontend

A089735 Self-convolution of A004148 (the RNA secondary structure numbers) with itself.

1, 2, 3, 6, 13, 28, 62, 140, 320, 740, 1728, 4068, 9645, 23010, 55195, 133042, 322078, 782758, 1909091, 4671098, 11462607, 28204212, 69569278, 171993316, 426111203, 1057757858, 2630527679, 6552998126, 16350465147, 40857321696, 102239831436

Offset: 0

Emeric Deutsch, Jan 07 2004

nonn

Number of (1,0) steps at level zero in all peakless Motzkin paths of length n+1 (can be easily expressed also in RNA secondary structure terminology). Example: a(3)=6 because in the four peakless Motzkin paths of length four, namely H'H'H'H', H'UHD, UHDH' and UHHD, where U=(1,1), D=(1,-1), H=(1,0), we have six H steps at level zero (indicated by H'). Lim_{n->infinity} a(n)/A004148(n) = 2.

Number of UHD's starting at level 0 in all peakless Motzkin paths of length n+3; here U=(1,1), H=(1,0), and D=(1,-1). Example: a(1)=2 because in HHHH, H(UHD), (UHD)H, and UHHD we have a total of 0+1+1+0 UHD's starting at level 0 (shown between parentheses).

I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261-272.
M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumeration en biologie moléculaire, Sem. Loth. Comb. B08l (1984) 79-86.
M. S. Waterman, Home Page (contains copies of his papers)

Cf. A004148, A190170.

a(n) = 2*Sum_{k=ceiling((n+1)/2)..n} binomial(k, n-k)*binomial(k+1, n-k+2)/k for n >= 1.
a(n) = A004148(n+2) - A004148(n+1) + A004148(n).
G.f. = 4/(1 - z + z^2 + sqrt(1 - 2z - z^2 - 2z^3 + z^4))^2.
G.f. = z^3*S^2, where S=S(z) is given by S = 1 + zS + z^2*S(S-1) (the g.f. of the RNA secondary structure numbers, A004148).
a(n) ~ 5^(1/4) * phi^(2*n+4) / (sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, May 29 2022
D-finite with recurrence (n+4)*a(n) +(-3*n-7)*a(n-1) +2*n*a(n-2) +3*(-n+1)*a(n-3) +2*(n-2)*a(n-4) +(-3*n+13)*a(n-5) +(n-6)*a(n-6)=0. - R. J. Mathar, Jul 26 2022

A190171 Number of peakless Motzkin paths of length n having no UHD's starting at level 0; here U=(1,1), H=(1,0), and D=(1,-1).

Original entry on oeis.org

1, 1, 1, 1, 2, 5, 12, 27, 60, 135, 309, 717, 1680, 3966, 9423, 22518, 54091, 130540, 316358, 769577, 1878497, 4599623, 11294640, 27807381, 68627188, 169746823, 420732391, 1044830875, 2599352149, 6477571270, 16167429874, 40411920571, 101153167258, 253522241008

Offset: 0

Emeric Deutsch, May 06 2011

nonn

a(n)=A190170(n,0).

			a(4)=2 because we have HHHH and UHHD.

Cf. A190170.

p1 := G-1-z*G-z^2*G*(S-1-z): p2 := S-1-z*S-z^2*S*(S-1): r := resultant(p1, p2, S): g := RootOf(r, G): Gser := simplify(series(g, z = 0, 40)): seq(coeff(Gser, z, n), n = 0 .. 33);

CoefficientList[Series[2/(1 + Sqrt[(1 + (-3 + x)*x)*(1 + x + x^2)] + x*(-1 + x + 2*x^2)), {x, 0, 40}], x] (* Vaclav Kotesovec, May 29 2022 *)

G.f. G=G(z) is obtained by elimitaing S from the equations G=1+zG+z^2*G(S-1-z) and S=1+zS+z^2*S(S-1).
From Vaclav Kotesovec, May 29 2022: (Start)
G.f.: 2/(1 + sqrt((1 + (-3 + x)*x)*(1 + x + x^2)) + x*(-1 + x + 2*x^2)).
a(n) ~ 5^(1/4) * phi^(2*n+6) / (18 * sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. (End)
Conjecture D-finite with recurrence (n+2)*a(n) +(-n+1)*a(n-1) +2*(-2*n-1)*a(n-2) +9*a(n-3) +(-n+1)*a(n-4) -9*a(n-5) +2*(-2*n+5)*a(n-6) +(-n+1)*a(n-7) +(n-4)*a(n-8)=0. - R. J. Mathar, Jul 22 2022

cp's OEIS Frontend

A089735 Self-convolution of A004148 (the RNA secondary structure numbers) with itself.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A190171 Number of peakless Motzkin paths of length n having no UHD's starting at level 0; here U=(1,1), H=(1,0), and D=(1,-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula