|
| |
|
|
A110236
|
|
Number of (1,0) steps in all peakless Motzkin paths of length n (can be easily translated into RNA secondary structure terminology).
|
|
9
| |
|
|
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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| Number of UHD's in all peakless Motzkin paths of length n+2; here U=(1,1), H=(1,0), and D=(1,-1). Example: a(2)=2 because in HHHH, HUHD, UHDH, and UHHD we have a total of 0+1+1+0 UHD's.
a(n)=sum(k*A110235(n,k),k=1..n).
a(n)=sum(k*A190172(n+2,k),k>=0).
|
|
|
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+1)=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, index corrected Jul 13 2011
a(n+1) =sum{k=0..,floor(n/2), C(n-k+1,k+1)*C(n-k,k)}; a(n+1):=sum{k=0..n, C(k+1,n-k+1)*C(k,n-k)}. [From Paul Barry (pbarry(AT)wit.ie), Aug 17 2009, indices corrected Jul 13 2011]
G.f. = z*S^2/(1-z^2*S^2), where S=1+zS+z^2*S(S-1) (the g.f. of the RNA secondary structure numbers; A004148).
a(n) = -f_{n}(-n) with f_1(n)=n and f_{p}(n)= (n+p-1)*(n+p+1-1)^2 *(n+p+2-1)^2*...*(n+p+(p-1)-1)^2/(p!*(p-1)!) +f_{p-1}(n) for p > 1. [Alzhekeyev Ascar M, Jun 27 2011]
Let A=floor(n/2), R=n-1, B=A-R/2+1, C=A+1, D=A-R and Z=1 if n mod 2 = 1, otherwise Z = n*(n+2)/4. Then a(n) = Z*Hypergeometric([1,C,C+1,D,D-1],[B,B,B-1/2,B-1/2],1/16). - Peter Luschny, Jan 14 2012
|
|
|
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, A190172, A203611, bisection of A202411.
Sequence in context: A052542 A178036 A191625 * A191828 A065161 A191758
Adjacent sequences: A110233 A110234 A110235 * A110237 A110238 A110239
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 17 2005
|
| |
|
|
