|
|
A089742
|
|
Number of subwords UHH...HD in all peakless Motzkin paths of length n+3, where U=(1,1), D=(1,-1) and H=(1,0).
|
|
1
|
|
|
1, 3, 7, 17, 41, 99, 242, 596, 1477, 3681, 9215, 23155, 58368, 147530, 373768, 948882, 2413264, 6147414, 15682008, 40056238, 102434119, 262228051, 671945055, 1723350315, 4423518544, 11362907022, 29208834520, 75131251334, 193370093508
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
This sequence can also be easily expressed using RNA secondary structure terminology.
|
|
LINKS
|
M. S. Waterman, Home Page (contains copies of his papers)
|
|
FORMULA
|
G.f.= g^2/[(1-z)(1-z^2*g^2)], where g=(1-z+z^2-sqrt(1-2z-z^2-2*z^3+z^4))/(2z^2) is the g.f. of sequence A004148 (RNA secondary structures).
a(n) = Sum_{m=0..n+2 }(Sum_{j=1..m/2}(j*Sum_{i=0..m/2-j} ((binomial(2*j+2*i,i)*Sum_{k=0..m-2*j-2*i}(binomial(k,m-k-2*j-2*i)*binomial(k+2*j+2*i-1,k)*(-1)^(k-m)))/(j+i)))). - Vladimir Kruchinin, Mar 07 2016
D-finite with recurrence (n+2)*a(n) +(-4*n-5)*a(n-1) +(5*n-1)*a(n-2) +(-5*n+7)*a(n-3) +(5*n-3)*a(n-4) +(-5*n+9)*a(n-5) +(4*n-13)*a(n-6) +(-n+4)*a(n-7)=0. - R. J. Mathar, Jul 24 2022
|
|
EXAMPLE
|
a(1)=3 because in the four peakless Motzkin paths of length 4, namely HHHH, H(UHD), (UHD)H and (UHHD), we have altogether three subwords of the required form (shown between parentheses).
|
|
PROG
|
(Maxima)
a(n):=sum(sum(j*sum((binomial(2*j+2*i, i)*sum(binomial(k, m-k-2*j-2*i)*binomial(k+2*j+2*i-1, k)*(-1)^(k-m), k, 0, m-2*j-2*i))/(j+i), i, 0, m/2-j), j, 1, m/2), m, 0, n+2); /* Vladimir Kruchinin, Mar 07 2016 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|