|
|
A114711
|
|
Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n and having k weak ascents (1 <= k <= ceiling(n/3)).
|
|
0
|
|
|
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;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
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.
|
|
LINKS
|
|
|
FORMULA
|
Row n contains ceiling(n/3) terms.
Row sums yield the RNA secondary structure numbers (A004148).
Column 1 yields the Fibonacci numbers (A000045).
T(3n+1,n+1) = A000108(n) (the Catalan numbers).
Sum_{k=1..ceiling(n/3)} k*T(n,k) = A051286(n-1) (n >= 1).
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
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|