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

Author

Emeric Deutsch, Apr 04 2007

Keywords

• nonn
• tabl

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.

Examples

			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;
		

Links

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

Crossrefs

Cf. A002212, A129166, A129167.

Programs

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

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).