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,4

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

Links

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

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

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

Example

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

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

Crossrefs

Cf. A004148.

Sequence in context: A136750 A274115 A097107 * A182900 A202843 A247297

Adjacent sequences: A098080 A098081 A098082 * A098084 A098085 A098086

Keyword

nonn,tabf

Author

Emeric Deutsch, Sep 13 2004

Status

approved