A098071 Triangle read by rows: T(n,k) is number of peakless Motzkin paths of length n and having k uhh...hd's starting at level 0, where u=(1,1), h=(1,0) and d=(1,-1) (can be easily expressed using RNA secondary structure terminology).

1, 1, 1, 1, 1, 1, 3, 2, 6, 6, 10, 1, 17, 15, 5, 44, 23, 15, 107, 42, 35, 1, 252, 94, 70, 7, 588, 233, 129, 28, 1376, 585, 237, 84, 1, 3245, 1441, 468, 210, 9, 7717, 3481, 1026, 466, 45, 18485, 8319, 2434, 968, 165, 1, 44535, 19835, 5972, 1984, 495, 11, 107796, 47436

Offset

0,7

Comments

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

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

Row n has 1+floor(n/3) terms.

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

Links

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

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.

Formula

G.f.: G=G(t, z) satisfies aG^2 + bG + c = 0, where a=z^2*(1-z-z^2+2z^3-tz+2tz^2-2tz^3-tz^4+t^2z^4), b=-(1-z)(1-2z+2z^2+z^3-2tz^3), c=(1-z)^2.

The g.f. H(t,z), counting peakless Motzkin paths by the number of UH^bD (b is fixed) starting at level 0 (marked by t) and by length (marked by z), satisfies the equation H=1+zH+z^2*H(g-1-z^b + tz^b), where g=1+zg+z^2*g(g-1).

Example

Triangle starts:
1;
1;
1;
1,1;
1,3;
2,6;
6,10,1;
17,15,5;
44,23,15;
107,42,35,1;
T(6,2)=1 because we have (uhd)(uhd) (the two pertinent subwords are shown between parentheses).

Crossrefs

Cf. A004148, A190159, A187260.

Sequence in context: A102022 A064684 A371944 * A347741 A347742 A286970

Adjacent sequences: A098068 A098069 A098070 * A098072 A098073 A098074

Keyword

nonn,tabf

Author

Emeric Deutsch, Sep 13 2004

Status

approved