|
|
A128731
|
|
Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n having k DL's (n>=0; 0<=k<=floor(n/2)).
|
|
1
|
|
|
1, 1, 2, 1, 5, 5, 14, 21, 1, 42, 84, 11, 132, 330, 80, 1, 429, 1287, 484, 19, 1430, 5005, 2639, 210, 1, 4862, 19448, 13468, 1780, 29, 16796, 75582, 65688, 12852, 450, 1, 58786, 293930, 310080, 83334, 5065, 41, 208012, 1144066, 1428306, 500346, 46640
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of the path is defined to be the number of its steps.
|
|
LINKS
|
E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203
|
|
FORMULA
|
G.f.: G=G(t,z) satisfies z^2*G^3-z(2-z)G^2+(1-tz^2)G-1+z=0.
Row n has 1+floor(n/2) terms.
Row sums yield the sequence A002212.
T(n,0) = A000108 (the Catalan numbers).
T(n,1) = binomial(2n-1,n-2) = A002054(n-1).
Sum_{k=0..floor(n/2)} k*T(n,k) = A128732(n).
|
|
EXAMPLE
|
T(3,1)=5 because we have UDUUDL, UUUDLD, UUDUDL, UUUDDL and UUUDLL (the other 5 paths of semilength 3 are Dyck paths which, obviously, contain no DL's).
Triangle starts:
1;
1;
2, 1;
5, 5;
14, 21, 1;
42, 84, 11;
132, 330, 80, 1;
|
|
MAPLE
|
eq:=z^2*G^3-z*(2-z)*G^2+(1-t*z^2)*G-1+z=0:
G:=RootOf(eq, G): Gser:=simplify(series(G, z=0, 17)):
for n from 0 to 13 do P[n]:=sort(coeff(Gser, z, n)) od:
for n from 0 to 13 do seq(coeff(P[n], t, j), j=0..floor(n/2)) od;
# yields sequence in triangular form
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|