login
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
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
Emeric Deutsch, Mar 31 2007
STATUS
approved