|
| |
|
|
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(n-3) 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, 207-237.
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, Polynomes orthogonaux at problemes d'enumeration en biologie moleculaire, Sem. Loth. Comb. B08l (1984) 79-86.
M. S. Waterman, Home Page (contains copies of his papers)
|
|
|
FORMULA
|
G.f.: 2/[2-t-2z+tz+tz^2+tsqrt(1-2z-z^2-2z^3+z^4)].
Columns k=0, 1, 2, ... have g.f.: z^(2k)*(g-1)^k/(1-z)^(k+1), where g=(1-z+z^2-sqrt(1-2z-z^2-2z^3+z^4))/(2z^2) is the g.f. of A004148.
G.f.: 1/[1-z-tz^2*(g-1)], 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(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:=(1-z+z^2-sqrt(1-2*z-z^2-2*z^3+z^4))/2/z^2: G:=simplify(1/(1-z-t*z^2*(g-1))): 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
|
| |
|
|
