A110333 Triangle read by rows: T(n,k) (n,k>=0) = number of peakless Motzkin paths of length n having k valleys (i.e., (1,-1) followed by (1,1)) at level zero (can be easily translated into RNA secondary structure terminology).

1, 1, 1, 2, 4, 8, 16, 1, 33, 4, 70, 12, 152, 32, 1, 336, 82, 5, 754, 206, 18, 1714, 512, 56, 1, 3940, 1264, 163, 6, 9145, 3109, 456, 25, 21406, 7634, 1243, 88, 1, 50478, 18737, 3326, 284, 7, 119814, 46006, 8781, 868, 33, 286045, 113062, 22955, 2556, 129, 1, 686456

Offset

0,4

Comments

Row n (n >= 3) has floor(n/3) terms.

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

Links

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

W. R. Schmitt and M. S. Waterman, Linear trees and RNA secondary structure, Discrete Appl. Math., 51, 317-323, 1994.

P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.

M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumeration en biologie moléculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.

Formula

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

Sum_{k>=0} k*T(n,k) = A110335(n-6) for n >= 6, 0 otherwise.

G.f.: (1 + z^2*g - tz^2*g - z^2 + tz^2)/(1 - z - z^3*g - tz^2*g + tz^3*g + z^3 + tz^2 - tz^3), where g = 1 + zg + z^2*g(g-1) = (1 - z + z^2 - sqrt(1 - 2z - z^2 - 2z^3 + z^4))/(2z^2) is the g.f. of the RNA secondary structure numbers (A004148).

Example

T(10,2)=5 because we have HUH(DU)H(DU)HD, UH(DU)H(DU)HDH, UHH(DU)H(DU)HD, UH(DU)HH(DU)HD and UH(DU)H(DU)HHD, where U=(1,1), H=(1,0), D=(1,-1) and the valleys at level zero are shown between parentheses.
Triangle begins:
    1;
    1;
    1;
    2;
    4;
    8;
   16,  1;
   33,  4;
   70, 12;
  152, 32,  1;
  336, 62,  5;

Maple

g:=(1-z+z^2-sqrt(1-2*z-z^2-2*z^3+z^4))/2/z^2: G:=(1+z^2*g-z^2*g*t-z^2+t*z^2)/(1-z-z^3*g-t*z^2*g+t*z^3*g+z^3+t*z^2-t*z^3): Gser:=simplify(series(G, z=0, 23)): P[0]:=1: for n from 1 to 20 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 2 do print(1) od: for n from 3 to 20 do seq(coeff(t*P[n], t^k), k=1..floor(n/3)) od; # yields sequence in triangular form

Crossrefs

Cf. A004148, A110334, A110335.

Sequence in context: A317501 A097777 A089738 * A247292 A069783 A102251

Adjacent sequences: A110330 A110331 A110332 * A110334 A110335 A110336

Keyword

nonn,tabf

Author

Emeric Deutsch, Jul 20 2005

Extensions

Keyword tabf added by Michel Marcus, Apr 09 2013

Status

approved