A089737 Number of (1,1) steps starting at level zero in all peakless Motzkin paths of length n+3.

1, 3, 7, 17, 41, 98, 235, 565, 1362, 3294, 7992, 19450, 47475, 116204, 285178, 701585, 1730003, 4275162, 10586164, 26263365, 65273566, 162499838, 405185762, 1011815774, 2530219435, 6335642377, 15884284791, 39871297479, 100194076029

Offset

0,2

Comments

This sequence can be easily expressed also in RNA secondary structure terminology.

Lim_{n->infinity} a(n)/A004148(n) = sqrt(5).

Links

Table of n, a(n) for n=0..28.

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)

Formula

a(n) = Sum_{k=ceiling(n/2+1)..n+1} (5k-2n-2)*binomial(k,n+1-k) * binomial(k+1,n+3-k)/(k*(n+4-k)).

a(n) = A004148(n+5) - 2*A004148(n+4) + A004148(n+3) - A004148(n+2).

G.f.: 2/(1 - 3z + 2z^2 - 2z^3 + 2z^4 - z^5 + (1 - 2z + z^2 - z^3)*sqrt(1 - 2z - z^2 - 2z^3 + z^4)).

D-finite with recurrence -(n+7)*(86*n-51)*a(n) +3*(95*n^2+434*n-249)*a(n-1) +4*(-35*n^2-71*n-60)*a(n-2) +(59*n^2+209*n+1020)*a(n-3) +6*(-52*n^2+11*n+71)*a(n-4) +(113*n+119)*(n-3)*a(n-5)=0. - R. J. Mathar, Jul 24 2022

Example

a(2)=7 because in the eight peakless Motzkin paths of length 5, namely HHHHH, HHU'HD, HU'HHD, HU'HDH, U'HDHH, U'HHDH, U'HHHD and U'UHDD, where U=(1,1), D=(1,-1), H=(1,0), we have altogether seven U steps starting at level zero (indicated by U').

Crossrefs

Cf. A004148.

Sequence in context: A272480 A131056 A077851 * A123335 A001333 A078057

Adjacent sequences: A089734 A089735 A089736 * A089738 A089739 A089740

Keyword

nonn

Author

Emeric Deutsch, Jan 07 2004

Status

approved