A097777 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k U H^j Us for some j>0, where U=(1,1) and H=(1,0) (can be easily expressed using RNA secondary structure terminology).

1, 1, 1, 2, 4, 8, 16, 1, 32, 5, 65, 17, 134, 50, 1, 280, 136, 7, 592, 355, 31, 1264, 904, 114, 1, 2722, 2264, 378, 9, 5906, 5604, 1176, 49, 12900, 13752, 3504, 215, 1, 28344, 33530, 10112, 835, 11, 62608, 81358, 28468, 2997, 71, 138949, 196688, 78576, 10173, 361, 1

Offset: 0

Author

Emeric Deutsch, Sep 11 2004

Keywords

• nonn
• tabf

Comments

Row n contains floor(n/3) entries (n>=3).

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

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

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

Examples

			Triangle starts:
  1;
  1;
  1;
  2;
  4;
  8;
  16,1;
  32,5;
  65,17;
  134,50,1;
  280,136,7;
  ...
Row n has floor(n/3) terms, n>=3.
T(7,1)=5 because we have H(UHU)HDD, (UHU)HHDD, (UHU)HDHD, (UHU)HDDH and (UHHU)HDD, where U=(1,1), H=(1,0) and D=(1,-1); the U H^j U's 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, A098051, A187257

Programs

Maple

eq := G = 1+z*G+z^2*G*(G-1+(t-1)*(z*G-z/(1-z))): g := RootOf(eq, G): gser := simplify(series(g, z = 0, 23)): for n from 0 to 18 do P[n] := sort(coeff(gser, z, n)) end do: 1; 1; 1; for n from 3 to 18 do seq(coeff(P[n], t, k), k = 0 .. floor((1/3)*n)-1) end do; # yields sequence in triangular form

Formula

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

The generating function H=H(t,z) relative to the number of subwords of the form UH^bU for a fixed b>=1 satisfies H = 1+zH+z^2*H[H-1+(t-1)z^b*(H-1-zH)].