A089741 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k UHH...HD's, where U=(1,1), D=(1,-1) and H=(1,0) (can be easily expressed using RNA secondary structure terminology).
1, 1, 1, 1, 1, 1, 3, 1, 7, 1, 15, 1, 1, 31, 5, 1, 63, 18, 1, 127, 56, 1, 1, 255, 160, 7, 1, 511, 432, 34, 1, 1023, 1120, 138, 1, 1, 2047, 2816, 500, 9, 1, 4095, 6912, 1672, 55, 1, 8191, 16640, 5264, 275, 1, 1, 16383, 39424, 15808, 1205, 11, 1, 32767, 92160, 45696, 4797
Offset: 0
Examples
T(7,2)=5 because we have H(UHD)(UHD), (UHD)H(UHD), (UHD)(UHD)H, (UHD)(UHHD) and (UHHD)(UHD) (the required subwords are shown between parentheses). Triangle begins: 1; 1; 1; 1, 1; 1, 3; 1, 7; 1, 15, 1; 1, 31, 5; 1, 63, 18; 1, 127, 56, 1; 1, 255, 160, 7; ...
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.
Formula
G.f.: (1-2*z+2*z^2-t*z^3-sqrt((1-t*z^3)*(1-4*z+4*z^2-t*z^3)))/(2*z^2*(1-z)).