|
| |
|
|
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). 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.
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| Row sums yield A002212. 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*T(n,k),k=1..n)=A129162(n).
|
|
|
LINKS
| E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203
|
|
|
FORMULA
| 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
| Cf. A002212, A055010, A000079, A129162.
Sequence in context: A157011 A092821 A110552 * A103415 A054456 A096164
Adjacent sequences: A129158 A129159 A129160 * A129162 A129163 A129164
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Apr 03 2007
|
| |
|
|
