OFFSET
1,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.
Row sums yield A002212.
LINKS
E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203
FORMULA
T(n,1) = 1;
T(n,2) = 3*2^(n-2) - 1 = A055010(n-1).
T(n,n) = 2^(n-1) = A000079(n-1).
Sum_{k=1..n} k*T(n,k) = A129162(n).
Column k has g.f. h[k]=H[k]-H[k-1], where H[k]=(1-z+zH[k-1])/(1-zH[k-1]), H[0]=1 (H[k] is the g.f. of paths of height at most k). For example, h[1]=z/(1-z); h[2]=z^2*(2-z)/[(1-z)(1-2z)]; h[3]=z^3*(2-z)^2/[(1-2z)(1-3z+z^2-z^3)].
EXAMPLE
T(3,2)=5 because we have UDUUDD, UDUUDL, UUDDUD, UUDUDD and UUDUDL.
Triangle starts:
1;
1, 2;
1, 5, 4;
1, 11, 16, 8;
1, 23, 53, 44, 16;
MAPLE
H[0]:=1: for k from 1 to 11 do H[k]:=simplify((1+z*H[k-1]-z)/(1-z*H[k-1])) od: for k from 1 to 11 do h[k]:=factor(simplify(H[k]-H[k-1])) od: for k from 1 to 11 do hser[k]:=series(h[k], z=0, 15) od: T:=(n, k)->coeff(hser[k], z, n): for n from 1 to 11 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Apr 03 2007
STATUS
approved