login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 4 01:48 EST 2021. Contains 341773 sequences. (Running on oeis4.)