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,2

Comments

Row n has ceiling(n/2)-1 terms. Row sums yield A110239.

Links

Table of n, a(n) for n=3..56.

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.

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).

Example

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;

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;

Crossrefs

Cf. A004148, A110239, A110237.

Sequence in context: A210197 A324715 A316665 * A077505 A309376 A247382

Adjacent sequences: A110235 A110236 A110237 * A110239 A110240 A110241

Keyword

nonn,tabf

Author

Emeric Deutsch, Jul 17 2005

Status

approved