BBC Russian

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).

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-2z-z^2-2z^3+z^4))/2/z^2: G:=simplify(1/(1-z-tz^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`