|
Search: id:A114712
|
|
|
| A114712 |
|
Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n and having k ascents (0<=k<=floor(n/3)). A Motzkin path of length n is a lattice path from (0,0) to (n,0) consisting of U=(1,1), D=(1,-1) and H=(1,0) steps and never going below the x-axis. An ascent in a Motzkin path is a maximal sequence of consecutive U steps. |
|
+0
2
|
|
| 1, 1, 1, 1, 1, 1, 3, 1, 7, 1, 14, 2, 1, 26, 10, 1, 46, 35, 1, 79, 100, 5, 1, 133, 254, 35, 1, 221, 595, 161, 1, 364, 1316, 588, 14, 1, 596, 2788, 1862, 126, 1, 972, 5714, 5334, 714, 1, 1581, 11408, 14190, 3150, 42, 1, 2567, 22300, 35652, 11850, 462, 1, 4163, 42842
(list; graph; listen)
|
|
|
OFFSET
|
0,7
|
|
|
COMMENT
|
Row n contains 1+floor(n/3) terms. Row sums yield the RNA secondary structure numbers (A004148). T(3n,n)=A000108(n) (the Catalan numbers). Sum(k*T(n,k),k=0..floor(n/3))=A114713(n-3) (n>=3).
|
|
REFERENCES
|
I. L. Hofacker, P. Schuster, and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26, 1979, 261-272.
M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux et problemes d'enumeration en biologie moleculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.
|
|
FORMULA
|
G.f.=G=G(t, z) satisfies G=1+zG+z^2*(tzG+G-1-zG)G.
|
|
EXAMPLE
|
T(6,2)=2 because we have (U)HD(U)HD and (U)H(U)HDD (the ascents are shown between parentheses).
Triangle begins:
1;
1;
1;
1,1;
1,3;
1,7;
1,14,2;
|
|
MAPLE
|
G:=(1+z^2-z-sqrt(1-z^2-2*z+z^4+2*z^3-4*z^3*t))/2/z^2/(z*t+1-z): 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^j), j=1..1+floor(n/3)) od; # yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A004148, A000108, A114713.
Sequence in context: A086665 A050521 A098093 this_sequence A089741 A089736 A094024
Adjacent sequences: A114709 A114710 A114711 this_sequence A114713 A114714 A114715
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 27 2005
|
|
|
Search completed in 0.002 seconds
|
