login
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, 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,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)).
EXAMPLE
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;
...
CROSSREFS
Row sums yield A004148. Column 1 is A000225, column 2 is A001793.
Sequence in context: A160627 A114712 A321452 * A089736 A205479 A094024
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jan 08 2004
STATUS
approved