A098051 Number of peakless Motzkin paths with no U H...HU's where U=(1,1) and H=(1,0) (can be easily expressed using RNA secondary structure terminology).

1, 1, 1, 2, 4, 8, 16, 32, 65, 134, 280, 592, 1264, 2722, 5906, 12900, 28344, 62608, 138949, 309692, 692905, 1555718, 3504016, 7915182, 17927154, 40702926, 92623758, 211217180, 482593474, 1104640484, 2532768508, 5816447840

Offset

0,4

Links

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

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'énumération en biologie moléculaire, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]

Formula

G.f.: G=G(z) satisfies G=1+zG+z^2*G[G-1-zG+z/(1-z)].

D-finite with recurrence (n+2)*a(n) +5*(-n-1)*a(n-1) +2*(4*n+1)*a(n-2) -4*n*a(n-3) +2*(-2*n+11)*a(n-5) +2*(4*n-23)*a(n-6) +4*(-n+6)*a(n-7)=0. - R. J. Mathar, Jul 24 2022

Example

a(4)=4 because we have HHHH, UHDU, HUHD and UHHD; a(6)=16 because among all 17 peakless Motzkin paths of length 6 (see A004148) only (UHU)HDD does not qualify.

Maple

G:=(1-2*z+2*z^2-2*z^3-sqrt(1-4*z+4*z^2-4*z^5+4*z^6))/2/z^2/(1-z)^2: Gser:=series(G, z=0, 35): 1, seq(coeff(Gser, z^n), n=1..32);

Crossrefs

Cf. A004148.

Sequence in context: A101333 A367652 A023421 * A329053 A084637 A100137

Adjacent sequences: A098048 A098049 A098050 * A098052 A098053 A098054

Keyword

nonn

Author

Emeric Deutsch, Sep 11 2004

Status

approved