|
Search: id:A110236
|
|
|
| A110236 |
|
Number of (1,0) steps in all peakless Motzkin paths of length n (can be easily translated into RNA secondary structure terminology). |
|
+0
3
|
|
| 1, 2, 4, 10, 24, 58, 143, 354, 881, 2204, 5534, 13940, 35213, 89162, 226238, 575114, 1464382, 3734150, 9534594, 24374230, 62377881, 159793932, 409717004, 1051405260, 2700168229, 6939388478, 17845927498, 45922416814, 118238842174
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
a(n)=sum(k*A110235(n,k),k=1..n).
|
|
REFERENCES
|
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, 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
|
a(n)=sum(k*T(n, k), k=1..n), where T(n, k)=[2/(n+k)]binomial((n+k)/2, k)*binomial((n+k)/2, k-1) for n+k mod 2 = 0 and T(n, k)=0 otherwise. G.f.=(1-z+z^2-Q)/(2zQ), where Q=sqrt(1-2z-z^2-2z^3+z^4).
a(n)=sum{k=0..n, sum{j=0..n-k, C(k+j,n-k-j)*C(k,n-k-j)}}; - Paul Barry (pbarry(AT)wit.ie), Oct 24 2006
a(n):=sum{k=0..,floor(n/2), C(n-k+1,k+1)*C(n-k,k)}; a(n):=sum{k=0..n, C(k+1,n-k+1)*C(k,n-k)}. [From Paul Barry (pbarry(AT)wit.ie), Aug 17 2009]
|
|
EXAMPLE
|
a(3)=4 because in the 2 (=A004148(3)) peakless Motzkin paths of length 3, namely HHH and UHD (where U=(1,1), H=(1,0) and D=(1,-1)), we have alltogether 4 H steps.
|
|
MAPLE
|
T:=proc(n, k) if n+k mod 2 = 0 then 2*binomial((n+k)/2, k)*binomial((n+k)/2, k-1)/(n+k) else 0 fi end:seq(add(k*T(n, k), k=1..n), n=1..33);
|
|
CROSSREFS
|
Cf. A004148, A110235, A089732.
Sequence in context: A165409 A163271 A052542 this_sequence A065161 A038373 A052987
Adjacent sequences: A110233 A110234 A110235 this_sequence A110237 A110238 A110239
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 17 2005
|
|
|
Search completed in 0.002 seconds
|
