|
| |
|
|
A129163
|
|
Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and pyramid weight k.
|
|
1
|
|
|
|
1, 1, 2, 2, 4, 4, 4, 11, 13, 8, 8, 29, 46, 38, 16, 16, 74, 150, 167, 104, 32, 32, 184, 461, 652, 554, 272, 64, 64, 448, 1354, 2344, 2535, 1724, 688, 128, 128, 1072, 3836, 7922, 10462, 9103, 5112, 1696, 256, 256, 2528, 10552, 25506, 40007, 42547, 30773, 14592
(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. A pyramid in a skew Dyck word (path) is a factor of the form U^h D^h, h being the height of the pyramid. A pyramid in a skew Dyck word w is maximal if, as a factor in w, it is not immediately preceded by a U and immediately followed by a D. The pyramid weight of a skew Dyck path (word) is the sum of the heights of its maximal pyramids.
Row sums yield A002212. T(n,1)=2^(n-2) (n>=2). T(n,n)=2^(n-1). Sum(k*T(n,k),k=1..n)=A129164(n). Pyramid weight in Dyck paths is considered in the Denise and Simion reference (see also A091866).
|
|
|
LINKS
|
E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203
|
|
|
FORMULA
|
G.f.=G-1, where G=G(t,z) is given by z(1-tz)G^2-(1-2tz+tz^2)G+(1-z)(1-tz)=0.
|
|
|
EXAMPLE
|
T(3,2)=4 because we have (UD)U(UD)L, U(UD)(UD)D, U(UD)(UD)L and U(UUDD)L (the maximal pyramids are shown between parentheses).
Triangle starts:
1;
1,2;
2,4,4;
4,11,13,8;
8,29,46,38,16;
|
|
|
MAPLE
|
eq:=z*(1-t*z)*G^2-(1-2*t*z+t*z^2)*G+(1-z)*(1-t*z)=0: G:=RootOf(eq, G): Gser:=simplify(series(G-1, z=0, 15)): for n from 1 to 11 do P[n]:=sort(expand(coeff(Gser, z, n))) od: for n from 1 to 11 do seq(coeff(P[n], t, j), j=1..n) od; # yields sequence in triangular form
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
