A110238 Triangle read by rows: T(n,k) (0 <= k <= ceiling(n/2)-2) is the number of (1,1) steps starting at level k in all peakless Motzkin paths of length n (can be easily translated into RNA secondary structure terminology).
1, 3, 7, 1, 17, 5, 41, 16, 1, 98, 46, 7, 235, 127, 29, 1, 565, 340, 99, 9, 1362, 893, 310, 46, 1, 3294, 2318, 921, 184, 11, 7992, 5968, 2640, 650, 67, 1, 19450, 15279, 7382, 2131, 309, 13, 47475, 38965, 20274, 6641, 1223, 92, 1, 116204, 99101, 54935, 19958, 4404
Offset: 3
Examples
T(5,1)=1 because in the 8 (=A004148(5)) peakless Motzkin paths of length 5, namely HHHHH, UHDHH, UHHDH, UHHHD, HUHDH, HUHHD, HHUHD and U(U)HDD (where U=(1,1), H=(1,0) and D=(1,-1)), we have altogether 1 U step starting at level 1 (shown between parentheses). Triangle starts: 1; 3; 7, 1; 17, 5; 41, 16, 1; 98, 46, 7;
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:=z^2*g^2*(g-1)/(1-t*z^2*g^2): Gser:=simplify(series(G,z=0,21)): for n from 1 to 17 do P[n]:=coeff(Gser,z^n) od: for n from 3 to 17 do seq(coeff(t*P[n],t^k),k=1..ceil(n/2)-1) od;
Formula
G.f.: z^2*g^2*(g-1)/(1-tz^2*g^2), 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).
Comments