|
Search: id:A114711
|
|
|
| A114711 |
|
Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n and having k weak ascents (1<=k<=ceil(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. A weak ascent in a Motzkin path is a maximal sequence of consecutive U and H steps. |
|
+0
1
|
|
| 1, 1, 2, 3, 1, 5, 3, 8, 9, 13, 22, 2, 21, 51, 10, 34, 111, 40, 55, 233, 130, 5, 89, 474, 380, 35, 144, 942, 1022, 175, 233, 1836, 2590, 700, 14, 377, 3522, 6260, 2450, 126, 610, 6666, 14570, 7770, 756, 987, 12473, 32870, 22890, 3570, 42, 1597, 23109, 72244
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
Row n contains ceil(n/3) terms. Row sums yield the RNA secondary structure numbers (A004148). Column 1 yields the Fibonacci numbers (A000045). Column 2 yields A001628. T(3n+1,n+1)=A000108(n) (the Catalan numbers). Sum(k*T(n,k),k=1..ceil(n/3))=A051286(n-1) (n>=1).
|
|
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=z(t+G)+z^2*G(1+G).
|
|
EXAMPLE
|
T(5,2)=3 because we have (UH)D(UU), (UHH)D(H) and (HUH)D(H) (the weak ascents are shown between parentheses).
Triangle begins:
1;
1;
2;
3,1;
5,3;
8,9;
13,22,2;
|
|
MAPLE
|
G:=(1-z-z^2-sqrt(1-2*z-z^2+2*z^3+z^4-4*t*z^3))/2/z^2: Gser:=simplify(series(G, z=0, 22)): for n from 1 to 18 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 18 do seq(coeff(P[n], t^j), j=1..ceil(n/3)) od; # yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A004148, A000045, A001628, A000108, A051286.
Adjacent sequences: A114708 A114709 A114710 this_sequence A114712 A114713 A114714
Sequence in context: A134734 A111609 A047706 this_sequence A002472 A060116 A114690
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 27 2005
|
|
|
Search completed in 0.002 seconds
|
