A129165 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k base pyramids.

1, 0, 1, 1, 1, 1, 5, 2, 2, 1, 19, 9, 4, 3, 1, 73, 37, 15, 7, 4, 1, 292, 147, 63, 24, 11, 5, 1, 1203, 598, 258, 100, 37, 16, 6, 1, 5065, 2497, 1067, 419, 152, 55, 22, 7, 1, 21697, 10633, 4507, 1762, 647, 224, 79, 29, 8, 1, 94274, 45980, 19379, 7528, 2765, 964, 322

Offset

0,7

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 base pyramid is a pyramid starting on the x-axis.

Row sums yield A002212.

Links

Table of n, a(n) for n=0..61.

E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203

Formula

T(n,0) = A129166(n).

Sum_{k=0..n} k*T(n,k) = A129167(n).

G.f.: G(t,z) = (1-z)(1 - z + zg)/(1 - z(1-z)g - tz), where g = 1 + zg^2 + z(g-1) = (1 - z - sqrt(1 - 6z + 5z^2))(2z).

Example

T(3,1)=2 because we have (UD)UUDL and (UUUDDD) (the base pyramids are shown between parentheses).
Triangle starts:
   1;
   0, 1;
   1, 1, 1;
   5, 2, 2, 1;
  19, 9, 4, 3, 1;

Maple

g:=(1-z-sqrt(1-6*z+5*z^2))/2/z: G:=(1-z)*(1-z+z*g)/(1-z*(1-z)*g-t*z): Gser:=simplify(series(G, z=0, 15)): for n from 0 to 11 do P[n]:=sort(expand(coeff(Gser, z, n))) od: for n from 0 to 11 do seq(coeff(P[n], t, j), j=0..n) od; # yields sequence in triangular form

Crossrefs

Cf. A002212, A129166, A129167.

Sequence in context: A324996 A359426 A058841 * A190288 A325499 A081119

Adjacent sequences: A129162 A129163 A129164 * A129166 A129167 A129168

Keyword

nonn,tabl

Author

Emeric Deutsch, Apr 04 2007

Status

approved