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, 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

Offset: 1

Author

Emeric Deutsch, Apr 03 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.

Row sums yield A002212.

Examples

			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;
		

Links

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

Crossrefs

Cf. A000079, A002212, A055010, A129162.

Programs

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

Formula

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