A110237 Triangle read by rows: T(n,k) (0 <= k <= ceiling(n/2)-1) is the number of (1,0) steps at level k in all peakless Motzkin paths of length n (can be easily translated into RNA secondary structure terminology).

1, 2, 3, 1, 6, 4, 13, 10, 1, 28, 24, 6, 62, 59, 21, 1, 140, 144, 62, 8, 320, 350, 174, 36, 1, 740, 852, 474, 128, 10, 1728, 2077, 1263, 410, 55, 1, 4068, 5072, 3318, 1240, 230, 12, 9645, 12412, 8634, 3608, 835, 78, 1, 23010, 30440, 22314, 10216, 2792, 376, 14

Offset

1,2

Comments

Row n has ceiling(n/2) terms. Row sums yield A110236.

Links

Table of n, a(n) for n=1..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'énumération 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*g^2/(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).

T(n,m) = (m+1)*Sum_{i=0..(n-1)/2-m}((binomial(2*m+2*i+2,i)*Sum_{k=0..n-2*m-2*i-1}(binomial(k,n-2*m-k-2*i-1)*binomial(2*m+k+2*i+1,k)*(-1)^(n-k-1)))/(m+i+1)). - Vladimir Kruchinin, Mar 07 2016

Example

T(5,1)=10 because in the 8 (=A004148(5)) peakless Motzkin paths of length 5, namely HHHHH, U(H)DHH, U(HH)DH, U(HHH)D, HU(H)DH, HU(HH)D, HHU(H)D and UUHDD (where U=(1,1), H=(1,0) and D=(1,-1)), we have altogether 10 H steps at level 1 (shown between parentheses).
Triangle starts:
   1;
   2;
   3,  1;
   6,  4;
  13, 10,  1;

Maple

g:=(1-z+z^2-sqrt(1-2*z-z^2-2*z^3+z^4))/2/z^2: G:=z*g^2/(1-t*z^2*g^2): Gser:=simplify(series(G, z=0, 20)): for n from 1 to 15 do P[n]:=coeff(Gser, z^n) od: for n from 1 to 15 do seq(coeff(t*P[n], t^k), k=1..ceil(n/2)) od;

Prog

(Maxima)
T(n, m):=(m+1)*sum((binomial(2*m+2*i+2, i)*sum(binomial(k, n-2*m-k-2*i-1)*binomial(2*m+k+2*i+1, k)*(-1)^(n-k-1), k, 0, n-2*m-2*i-1))/(m+i+1), i, 0, (n-1)/2-m); /* Vladimir Kruchinin, Mar 07 2016 */

Crossrefs

Cf. A004148, A110236.

Sequence in context: A205112 A173161 A116468 * A189970 A076631 A035485

Adjacent sequences: A110234 A110235 A110236 * A110238 A110239 A110240

Keyword

nonn,tabf

Author

Emeric Deutsch, Jul 17 2005

Status

approved