

A089736


Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n having k (1,1) steps starting at level zero (can be easily expressed also in RNA secondary structure terminology).


0



1, 1, 1, 1, 1, 1, 3, 1, 7, 1, 15, 1, 1, 31, 5, 1, 64, 17, 1, 134, 49, 1, 1, 286, 129, 7, 1, 623, 323, 31, 1, 1383, 787, 111, 1, 1, 3121, 1891, 351, 9, 1, 7142, 4517, 1026, 49, 1, 16536, 10777, 2848, 209, 1, 1, 38665, 25750, 7636, 769, 11, 1, 91166, 61700, 19999, 2565, 71
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,7


COMMENTS

Also, triangle read by rows: T(n,k) (0<=k<=floor(n/3)) is the number of RNA secondary structures of size n (i.e. with n nodes) having k arcs that are not covered by other arcs. E.g. T(5,1)=7 because we have (13)/2/4/5, (14)/2/3/5, (15)/2,3,4, 1/(24),3,5, 1/(25)/3/4, 1/2/(35)/4 and (15)/24/3; T(6,2)=1 because we have (13)/2/(46)/5 (the arcs that are not covered by other arcs are shown between parentheses).
Row n has 1+floor(n/3) terms. Sum(k*T(n,k),k=0..floor(n/3))=A089737(n3) for n>=3.


LINKS

Table of n, a(n) for n=0..62.
I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207237.
W. R. Schmitt and M. S. Waterman, Linear trees and RNA secondary structure, Discrete Appl. Math., 51, 317323, 1994.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261272.
M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux at problemes d'enumeration en biologie moleculaire, Sem. Loth. Comb. B08l (1984) 7986.
M. S. Waterman, Home Page (contains copies of his papers)


FORMULA

G.f.: 2/[2t2z+tz+tz^2+tsqrt(12zz^22z^3+z^4)].
Columns k=0, 1, 2, ... have g.f.: z^(2k)*(g1)^k/(1z)^(k+1), where g=(1z+z^2sqrt(12zz^22z^3+z^4))/(2z^2) is the g.f. of A004148.
G.f.: 1/[1ztz^2*(g1)], where g=1+zg+z^2*g(g1)=[1z+z^2sqrt(12zz^22z^3+z^4)]/(2z^2) is the g.f. of the RNA secondary structure numbers (A004148).


EXAMPLE

T(7,2)=5 because we have UHDUHDH, UHDHUHD, HUHDUHD, UHHDUHD, UHDUHHD, where U=(1,1), D=(1,1) and H=(1,0) (in these paths all U's start at level zero).
Triangle begins
1;
1;
1;
1,1;
1,3;
1,7;
1,15,1;
1,31,5;


MAPLE

g:=(1z+z^2sqrt(12*zz^22*z^3+z^4))/2/z^2: G:=simplify(1/(1zt*z^2*(g1))): Gser:=simplify(series(G, z=0, 22)): P[0]:=1: for n from 1 to 18 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 18 do seq(coeff(t*P[n], t^k), k=1..1+floor(n/3)) od;


CROSSREFS

Cf. A004148, A089737.
Sequence in context: A114712 A321452 A089741 * A205479 A094024 A297172
Adjacent sequences: A089733 A089734 A089735 * A089737 A089738 A089739


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Jan 07 2004, Jul 19 2005


EXTENSIONS

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 23 2007


STATUS

approved



