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

%I #20 Jul 26 2022 14:36:18

%S 1,2,3,6,13,28,62,140,320,740,1728,4068,9645,23010,55195,133042,

%T 322078,782758,1909091,4671098,11462607,28204212,69569278,171993316,

%U 426111203,1057757858,2630527679,6552998126,16350465147,40857321696,102239831436

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

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

%C 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).

%H I. L. Hofacker, P. Schuster and P. F. Stadler, <a href="https://doi.org/10.1016/S0166-218X(98)00073-0">Combinatorics of RNA secondary structures</a>, Discrete Appl. Math., 88, 1998, 207-237.

%H P. R. Stein and M. S. Waterman, <a href="https://doi.org/10.1016/0012-365X(79)90033-5">On some new sequences generalizing the Catalan and Motzkin numbers</a>, Discrete Math., 26 (1979), 261-272.

%H M. Vauchassade de Chaumont and G. Viennot, <a href="http://www.mat.univie.ac.at/~slc/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumeration en biologie moléculaire</a>, Sem. Loth. Comb. B08l (1984) 79-86.

%H M. S. Waterman, <a href="http://www.cmb.usc.edu/people/msw/Waterman.html">Home Page</a> (contains copies of his papers)

%F a(n) = 2*Sum_{k=ceiling((n+1)/2)..n} binomial(k, n-k)*binomial(k+1, n-k+2)/k for n >= 1.

%F a(n) = A004148(n+2) - A004148(n+1) + A004148(n).

%F G.f. = 4/(1 - z + z^2 + sqrt(1 - 2z - z^2 - 2z^3 + z^4))^2.

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

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

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

%Y Cf. A004148, A190170.

%K nonn

%O 0,2

%A _Emeric Deutsch_, Jan 07 2004