|
| |
|
|
A129161
|
|
Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having height k (1 <= k <= n).
|
|
1
|
|
|
|
1, 1, 2, 1, 5, 4, 1, 11, 16, 8, 1, 23, 53, 44, 16, 1, 47, 165, 186, 112, 32, 1, 95, 494, 725, 568, 272, 64, 1, 191, 1442, 2707, 2576, 1600, 640, 128, 1, 383, 4141, 9813, 11065, 8184, 4272, 1472, 256, 1, 767, 11763, 34827, 45961, 39026, 24208, 10976, 3328, 512
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
|
|
|
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).
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
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
