The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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:=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

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

Last modified March 30 21:40 EDT 2023. Contains 361623 sequences. (Running on oeis4.)