A190160 Number of peakless Motzkin paths of length n containing no subwords of type uh^ju or dh^jd (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, 15, 28, 53, 102, 199, 391, 773, 1537, 3075, 6189, 12525, 25473, 52037, 106737, 219761, 454041, 941089, 1956357, 4078010, 8522016, 17850512, 37471531, 78818748, 166102378, 350660371, 741503529, 1570402564, 3330730115, 7073941610, 15043298781

Offset

0,4

Comments

a(n)=A097100(n,0). F% G.f.: G=G(z) satisfies the equation G=1+zG+z^2*G[z+(1-z)^2*(G-zG-1)]/(1-z).

Links

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

Formula

Conjecture D-finite with recurrence (n+2)*a(n) +(-5*n-6)*a(n-1) +2*(4*n+3)*a(n-2) +(-2*n-9)*a(n-3) +(-8*n+25)*a(n-4) +6*(n-2)*a(n-

5) +9*(n-7)*a(n-6) +3*(-5*n+32)*a(n-7) +7*(n-7)*a(n-8) +(-n+8)*a(n-9)=0. - R. J. Mathar, Jul 22 2022

Example

a(6)=15 because among the 17 (=A004148(6)) peakless  Motzkin paths of length 6 only (uhu)hdd and uuh(dhd) have subwords of the forbidden type (shown between parentheses).

Maple

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

Crossrefs

Cf. A097100, A004148

Sequence in context: A268393 A118870 A171857 * A332052 A088532 A271364

Adjacent sequences: A190157 A190158 A190159 * A190161 A190162 A190163

Keyword

nonn

Author

Emeric Deutsch, May 05 2011

Status

approved