A098083 -id:A098083 - cp's OEIS frontend

A098056 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k subwords of the type uh^ju, dH^jd, or dh^ju for some j>0, where u=(1,1), d=(1,-1) and h=(1,0) (can be easily expressed using RNA secondary structure terminology).

1, 1, 1, 2, 4, 8, 15, 2, 27, 9, 1, 48, 29, 5, 84, 80, 21, 147, 198, 74, 4, 257, 463, 230, 27, 1, 451, 1033, 667, 125, 7, 796, 2235, 1811, 488, 43, 1413, 4727, 4694, 1676, 219, 6, 2526, 9828, 11700, 5317, 946, 54, 1, 4544, 20192, 28252, 15813, 3696, 326, 9, 8226, 41100

Offset: 0

Emeric Deutsch, Sep 11 2004

Row sums are the RNA secondary structure numbers (A004148).
T(n,0) = A098057(n).
Sum(k*T(n,k),k>=0) = A187259(n).

			Triangle starts:
  1;
  1;
  1;
  2;
  4;
  8;
  15,2;
  27,9,1;
  48,29,5;
  84.80,21;
  147,198,74,7;
  ...
It seems that the number r(n) of terms in row n>=3 is given by r(n)=n/2-1 if n=2 (mod 4) and r(n)=2*round(n/4)-1 otherwise (here round(m) is the nearest integer to m).
T(7,1)=9 because we have h(uhu)hdd, (uhhu)hdd, (uhu)hhdd, (uhu)hddh, uh(dhu)hd and the reflections of the first four paths in a vertical axis; here u=(1,1), h=(1,0), d=(1,-1) and the pertinent subwords are shown between parentheses.

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, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08; Sem. Loth. Comb. B08l (1984) 79-86.

Cf. A041048, A098057, A187259.

G.f.=G=G(t, z) satisfies G = 1 + zG + z^2*[H + 2tzH/(1-z)+t^2*z^2*H/(1-z)^2+ z/(1-z)][G-(1-t)zH/(1-z)^2], where H=(1-z)^2*G-1+z.
The 4-variate g.f. G(t,s,v,z) of peakless Motzkin paths, where t, s, v mark subwords of the types uH^ju, dH^jd, dH^ju, respectively, and z marks length, satisfies the equation
G = 1+zG+z^2*[H + (t+s)zH/(1-z)+tsz^2*H/(1-z)^2+z/(1-z)][G-(1-v)zH/(1-z)^2],
where H = (1-z)[(1-z)G-1]. As special cases we get the current sequence A098056 and the sequences A097777 and A098083.

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

Original entry on oeis.org

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

Emeric Deutsch, May 05 2011

nonn

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

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

Cf. A098083, A004148

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

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

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 5, 18, 58, 174, 500, 1399, 3843, 10421, 27997, 74699, 198267, 524135, 1381261, 3631068, 9526568, 24954538, 65283648, 170610003, 445484163, 1162396269, 3031267533, 7901082379, 20586262763, 53620039074, 139624131310, 363495081689, 946147596489, 2462387385085

Offset: 0

Emeric Deutsch, May 05 2011

nonn

a(n)=Sum(k*A098083(n,k), k>=0).

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

Cf. A098083, A004148

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

G.f.: G(z)=z^5*g^2*(g-1)^2/[(1-z)(1-z^2*g^2)], where g=1+zg+z^2*g(g-1).

Conjecture D-finite with recurrence -4*(n+1)*(n-7)*a(n) +(13*n^2-85*n+28)*a(n-1) +(-7*n^2+52*n-41)*a(n-2) +(5*n^2-41*n+67)*a(n-3) +(-13*n^2+103*n-197)*a(n-4) +(7*n-29)*(n-5)*a(n-5) -(n-5)*(n-6)*a(n-6)=0. - R. J. Mathar, Jul 22 2022

cp's OEIS Frontend

A098056 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k subwords of the type uh^ju, dH^jd, or dh^ju for some j>0, where u=(1,1), d=(1,-1) and h=(1,0) (can be easily expressed using RNA secondary structure terminology).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula