A098083 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k DHH...HU's, where U=(1,1), D=(1,-1) and H=(1,0) (can be easily expressed using RNA secondary structure terminology).
1, 1, 1, 2, 4, 8, 17, 36, 1, 77, 5, 167, 18, 365, 58, 805, 172, 1, 1790, 486, 7, 4008, 1331, 34, 9033, 3561, 141, 20477, 9370, 524, 1, 46663, 24350, 1810, 9, 106843, 62674, 5930, 55, 245691, 160126, 18652, 279, 567194, 406732, 56832, 1245, 1, 1314086, 1028360
Offset: 0
Examples
Triangle starts:
1;
1;
1;
2;
4;
8;
17;
36, 1;
77, 5;
167, 18
T(8,1)=5 because we have UH(DHU)HHD, HUH(DHU)HD, UH(DHHU)HD, UH(DHU)HDH and UHH(DHU)HD (the required subwords are shown between parentheses).
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, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]
Crossrefs
Cf. A004148.
Programs
-
Maple
eq := G = 1+z*G+z^2*(G-1)*(G-(1-t)*z*(G-1-z*G)/(1-z)): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 23)): for n from 0 to 20 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 20 do seq(coeff(P[n], t, j), j = 0 .. degree(P[n])) end do; # yields sequence in triangular form
Formula
G.f. = G = G(t, z) satisfies G = 1 + z*G + z^2*(G-1)*(G - (1-t)*z*(G-z*G-1)/(1-z)).
Comments