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

Author

Emeric Deutsch, Sep 11 2004

Keywords

• nonn

Examples

			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.
		

Links

• 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.]

Crossrefs

Cf. A004148.

Programs

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);

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