A190162 Number of peakless Motzkin paths of length n containing no subwords of type dh^ju (j>=1), where u=(1,1), h=(1,0), and d=(1,-1) (can be easily expressed using RNA secondary structure terminology).

1, 1, 1, 2, 4, 8, 17, 36, 77, 167, 365, 805, 1790, 4008, 9033, 20477, 46663, 106843, 245691, 567194, 1314086, 3054442, 7120951, 16647056, 39015476, 91654385, 215780420, 509033640, 1203085539, 2848445175, 6755095119, 16044373511, 38162885226, 90897048648

Offset

0,4

Comments

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

Links

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

Formula

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

D-finite with recurrence (n+2)*a(n) +5*(-n-1)*a(n-1) +2*(4*n+1)*a(n-2) +(-6*n+5)*a(n-3) +(8*n-27)*a(n-4) +2*(-7*n+31)*a(n-5) +(13*n-71)*a(n-6) +(-7*n+47)*a(n-7) +(3*n-25)*a(n-8) +(-n+9)*a(n-9)=0. - R. J. Mathar, Jul 22 2022

Example

a(7)=36 because among the 37 (=A004148(7)) peakless Motzkin paths of length 7 only uh(dhu)hd has a subword of the forbidden type (shown between parentheses).

Maple

eq := G = 1+z*G+z^2*(G-1)*((1-z)*G+z/(1-z)): G := RootOf(eq, G): Gser := series(G, z=0, 38): seq(coeff(Gser, z, n), n = 0 .. 33);

Crossrefs

Cf. A098083, A004148

Sequence in context: A226729 A063457 A262735 * A275691 A251691 A157904

Adjacent sequences: A190159 A190160 A190161 * A190163 A190164 A190165

Keyword

nonn

Author

Emeric Deutsch, May 05 2011

Status

approved