A129170 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n such that the sum of the height of the peaks is k (n >= 0; n <= k <= floor((n+1)^2/4)).

1, 0, 1, 0, 0, 3, 0, 0, 0, 8, 2, 0, 0, 0, 0, 21, 9, 6, 0, 0, 0, 0, 0, 55, 33, 29, 16, 4, 0, 0, 0, 0, 0, 0, 144, 111, 114, 84, 60, 18, 12, 0, 0, 0, 0, 0, 0, 0, 377, 355, 409, 356, 305, 199, 120, 58, 32, 8, 0, 0, 0, 0, 0, 0, 0, 0, 987, 1098, 1389, 1365, 1308, 1032, 843, 507, 372, 204, 120

Offset

0,6

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 n has 1 + floor((n+1)^2/4) terms, the first n of which are equal to 0.

Row sums yield A002212.

Links

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

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

Formula

T(n,n) = A088305(n) = A001906(n) = Fibonacci(2n) for n >= 1.

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

G.f.: G(t,z)=H(t,1,z), where H(t,x,z)=1+z[H(t,tx,z)-1+tx]H(t,x,z)+z[H(t,tx,z)-1] (H(t,x,z) is the trivariate g.f. for skew Dyck paths according to sum of the height of the peaks, number of peaks and semilength, marked by t,x and z, respectively).

Example

T(3,4)=2 because we have UUDUDD and UUDUDL.
Triangle starts:
  1;
  0,  1;
  0,  0,  3;
  0,  0,  0,  8,  2;
  0,  0,  0,  0, 21,  9,  6;
  0,  0,  0,  0,  0, 55, 33, 29, 16,  4;

Maple

H:=(1+z*h[1]-z)/(1-z*h[1]+z-z*t*x): for n from 1 to 11 do h[n]:=(1+z*h[n+1]-z)/(1-z*h[n+1]+z-z*t^(n+1)*x) od: h[12]:=0: x:=1: G:=simplify(H): Gser:=simplify(series(G, z=0, 11)): for n from 0 to 9 do P[n]:=sort(coeff(Gser, z, n)) od: for n from 0 to 9 do seq(coeff(P[n], t, j), j=0..floor((n+1)^2/4)) od; # yields sequence in triangular form

Crossrefs

Cf. A001906, A002212, A088305, A129171.

Sequence in context: A241663 A344976 A344876 * A342590 A209436 A229121

Adjacent sequences: A129167 A129168 A129169 * A129171 A129172 A129173

Keyword

nonn,tabf

Author

Emeric Deutsch, Apr 07 2007

Status

approved