|
| |
|
|
A171854
|
|
Number of ladders in all peakless Motzkin paths of length n (n>=0).
|
|
1
|
|
|
|
0, 0, 0, 1, 3, 7, 19, 50, 129, 334, 862, 2220, 5715, 14706, 37836, 97353, 250535, 644905, 1660558, 4277165, 11020698, 28406449, 73245390, 188928736, 487492213, 1258305122, 3248994414, 8391747865, 21681628237, 56035444491, 144864062529
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
A string of consecutive up steps U_1, U_2, ..., U_m and their matching down steps D_1, D_2, ..., D_m are said to form a ladder if (i) D_1, D_2, ..., D_m are consecutive steps and (ii) the sequence of pairs (U_j, D_j) (j=1,2,...,m) is maximal. For example, in the path (UU)[U]H[D]H(DD), where U=(1,1), H=(1,0), D=(1,-1), we have 2 ladders, shown between parentheses and square brackets, respectively (can be easily expressed also in RNA secondary structure terminology).
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f. = z^2*(1-z^2)*g^2*(g-1)/(1-z^2*g^2), where g=g(z) is the g.f. of the number of peakless Motzkin paths (A004148), defined by g = 1 + z*g + z^2*g*(g-1). See also eq. (65) in the Hofacker et al. reference.
Conjecture D-finite with recurrence -(n+2)*(1390*n-8929)*a(n) +(4884*n^2-25542*n-20107)*a(n-1) +(60*n^2-6110*n-2249)*a(n-2) +(-5080*n^2+49134*n-115735)*a(n-3) +(-8476*n^2+66210*n-98877)*a(n-4) +(-3652*n^2+41338*n-109281)*a(n-5) +(2878*n-9993)*(n-7)*a(n-6)=0. - R. J. Mathar, Jul 22 2022
|
|
|
EXAMPLE
|
a(5)=7 because in the eight (=A004148(5)) peakless Motzkin paths of length 5, i.e. HHHHH, HH(U)H(D), H(U)HH(D), H(U)H(D)H, (U)H(D)HH, (U)HH(D)H, (U)HHH(D) and (UU)H(DD), each path, with the exception of the first, has 1 ladder (shown between parentheses).
|
|
|
MAPLE
|
eq := g = 1+z*g+z^2*g*(g-1): g := RootOf(eq, g): G := z^2*(1-z^2)*g^2*(g-1)/(1-z^2*g^2): Gser := series(G, z = 0, 35): seq(coeff(Gser, z, n), n = 0 .. 32);
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
