A098076 Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n and height k (can be easily expressed using RNA secondary structure terminology).

1, 1, 1, 1, 1, 1, 3, 1, 6, 1, 1, 11, 5, 1, 20, 15, 1, 1, 36, 38, 7, 1, 64, 91, 28, 1, 1, 113, 211, 89, 9, 1, 199, 477, 255, 45, 1, 1, 350, 1059, 690, 172, 11, 1, 615, 2321, 1797, 572, 66, 1, 1, 1080, 5037, 4555, 1754, 295, 13, 1, 1896, 10847, 11320, 5098, 1118, 91, 1, 1, 3328

Offset

0,7

Comments

Row sums are the RNA secondary structure numbers (A004148). Column 1 without the zeros yields A077855.

Links

Alois P. Heinz, Rows n = 0..200, flattened

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.: 1+sum(t^j*z^(2j+1)/[P(j)*P(j+1)], j=0..infinity), where P(j) are polynomials in z defined by P(0)=1, P(1)=1-z, P(j)=(1-z+z^2)P(j-1) -z^2*P(j-2), j=2, 3, ... .

Example

Triangle starts:
1;
1;
1;
1,   1;
1,   3;
1,   6,   1;
1,  11,   5;
1,  20,  15,   1;
1,  36,  38,   7;
1,  64,  91,  28,  1;
1, 113, 211,  89,  9;
1, 199, 477, 255, 45,  1;
Row n >0 has ceil(n/2) terms.
T(6,2) = 5 because the peakless Motzkin paths of length 6 and height 2 are HUUHDD, UHUHDD, UUHHDD, UUHDDH, UUHDHD, where U=(1,1), H=(1,0) and D=(1,-1).

Maple

P[0]:=1: P[1]:=sort(1-z): for j from 2 to 30 do P[j]:=sort(expand((1-z+z^2)*P[j-1]-z^2*P[j-2])) od: G:=1+sum(t^i*z^(2*i+1)/P[i]/P[i+1], i=0..25): Gser:=simplify(series(G, z=0, 21)): Q[0]:=1: for m from 1 to 18 do Q[m]:=sort(coeff(Gser, z^m)) od: 1, seq(seq(coeff(t*Q[n], t^k), k=1..ceil(n/2)), n=1..16);

Mathematica

max = 16; p[0] = 1; p[1] := 1 - z; p[j_] := p[j] = (1 - z + z^2)*p[j - 1] - z^2*p[j - 2]; gf = 1 + Sum[t^j*z^(2*j + 1)/(p[j]*p[j + 1]), {j, 0, max}]; se = Series[gf, {t, 0, max}, {z, 0, max}]; CoefficientList[se, {z, t}] // DeleteCases[#, 0, 2] & // Flatten (* Jean-François Alcover, Jun 25 2013 *)

Crossrefs

Cf. A004148, A077855.

Sequence in context: A034839 A089732 A158905 * A171852 A010287 A130270

Adjacent sequences: A098073 A098074 A098075 * A098077 A098078 A098079

Keyword

nonn,tabf

Author

Emeric Deutsch, Sep 13 2004

Status

approved