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
Examples
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).
Programs
-
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);
Formula
G.f.: G=G(z) satisfies the equation G=1+zG+z^2*G[z+(1-z)^2*(G-zG-1)]/(1-z).
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
Comments