A098083 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k DHH...HU's, 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, 17, 36, 1, 77, 5, 167, 18, 365, 58, 805, 172, 1, 1790, 486, 7, 4008, 1331, 34, 9033, 3561, 141, 20477, 9370, 524, 1, 46663, 24350, 1810, 9, 106843, 62674, 5930, 55, 245691, 160126, 18652, 279, 567194, 406732, 56832, 1245, 1, 1314086, 1028360

Offset: 0

Author

Emeric Deutsch, Sep 13 2004

Keywords

• nonn
• tabf

Comments

Row n >= 3 has ceiling((n-2)/4) terms.

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

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

Sum_{k>=0} k*T(n,k) = A190163(n).

Examples

			Triangle starts:
    1;
    1;
    1;
    2;
    4;
    8;
   17;
   36,  1;
   77,  5;
  167, 18
T(8,1)=5 because we have UH(DHU)HHD, HUH(DHU)HD, UH(DHHU)HD, UH(DHU)HDH and UHH(DHU)HD (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, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]

Crossrefs

Cf. A004148.

Programs

Maple

eq := G = 1+z*G+z^2*(G-1)*(G-(1-t)*z*(G-1-z*G)/(1-z)): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 23)): for n from 0 to 20 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 20 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 + z*G + z^2*(G-1)*(G - (1-t)*z*(G-z*G-1)/(1-z)).