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
Examples
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;
Links
- 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.
Programs
-
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
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).
Extensions
Keyword tabf added by Michel Marcus, Apr 09 2013
Comments