A128731 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n having k DL's (n>=0; 0<=k<=floor(n/2)).

1, 1, 2, 1, 5, 5, 14, 21, 1, 42, 84, 11, 132, 330, 80, 1, 429, 1287, 484, 19, 1430, 5005, 2639, 210, 1, 4862, 19448, 13468, 1780, 29, 16796, 75582, 65688, 12852, 450, 1, 58786, 293930, 310080, 83334, 5065, 41, 208012, 1144066, 1428306, 500346, 46640

Offset

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

Links

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

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

Formula

G.f.: G=G(t,z) satisfies z^2*G^3-z(2-z)G^2+(1-tz^2)G-1+z=0.

Row n has 1+floor(n/2) terms.

Row sums yield the sequence A002212.

T(n,0) = A000108 (the Catalan numbers).

T(n,1) = binomial(2n-1,n-2) = A002054(n-1).

Sum_{k=0..floor(n/2)} k*T(n,k) = A128732(n).

Example

T(3,1)=5 because we have UDUUDL, UUUDLD, UUDUDL, UUUDDL and UUUDLL (the other 5 paths of semilength 3 are Dyck paths which, obviously, contain no DL's).
Triangle starts:
    1;
    1;
    2,   1;
    5,   5;
   14,  21,  1;
   42,  84, 11;
  132, 330, 80, 1;

Maple

eq:=z^2*G^3-z*(2-z)*G^2+(1-t*z^2)*G-1+z=0:
G:=RootOf(eq, G): Gser:=simplify(series(G, z=0, 17)):
for n from 0 to 13 do P[n]:=sort(coeff(Gser, z, n)) od:
for n from 0 to 13 do seq(coeff(P[n], t, j), j=0..floor(n/2)) od;
# yields sequence in triangular form

Crossrefs

Cf. A000108, A002054, A002212, A128732.

Sequence in context: A096976 A052547 A119245 * A129157 A086905 A167638

Adjacent sequences: A128728 A128729 A128730 * A128732 A128733 A128734

Keyword

nonn,tabf

Author

Emeric Deutsch, Mar 31 2007

Status

approved