A097100 Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n containing k subwords of the type U H^j U or D H^j D for some j>0, 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, 2, 28, 8, 1, 53, 24, 5, 102, 62, 21, 199, 152, 68, 4, 391, 366, 196, 24, 1, 773, 868, 531, 104, 7, 1537, 2032, 1393, 368, 43, 3075, 4694, 3593, 1172, 195, 6, 6189, 10732, 9120, 3528, 754, 48, 1, 12525, 24348, 22822, 10224, 2632, 272, 9

Offset: 0

Author

Emeric Deutsch, Sep 15 2004

Keywords

• nonn
• tabf

Comments

Row sums are the RNA secondary structure numbers (A004148).

T(n,0)=A190160(n).

Sum(k*T(n,k),k>=0)=A190161(n).

The generating function G=G(t,s,z) relative to the number of subwords of the form uh^bu (marked by t) and dh^bd (marked by s) for a fixed b>=1, satisfies G = 1+zG+z^2*G[z/(1-z) + (w^2+twz^b+swz^b+tsz^{2b})H], where H=(1-z)[(1-z)G-1] and w = 1/(1-z) - z^b.

Examples

			Triangle starts:
  1;
  1;
  1;
  2;
  4;
  8;
  15,2;
  28,8,1;
  53,24,5;
  ...
It seems that, except for the first 3 rows, rows 4n-1, 4n, 4n+1 have 2n-1 terms and rows 4n+2 have 2n terms (n=1,2,...).
T(8,2)=5 because we have (UHU)H(DHD)H, (UHU)HH(DHD), H(UHU)H(DHD), (UHHU)H(DHD) and (UHU)H(DHHD); the required subwords are shown between parentheses.
		

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

Crossrefs

Cf. A004148, A190160, A190161.

Programs

Maple

eq := G = 1+z*G+z^2*G*(z+(1-z+t*z)^2*(G-z*G-1))/(1-z): G:= RootOf(eq,G): Gser := simplify(series(G,z=0,20)): for n from 0 to 19 do P[n] := sort(coeff(Gser,z,n)) end do: for n from 0 to 19 do seq(coeff(P[n],t,j), j=0 .. degree(P[n])) end do; # yields sequence in triangular form

Formula

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