A128753 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k UDUDU's (n >= 0; 0 <= k <= n-2 for n >= 2).

1, 1, 3, 9, 1, 31, 4, 1, 113, 19, 4, 1, 431, 86, 21, 4, 1, 1697, 393, 101, 23, 4, 1, 6847, 1800, 492, 116, 25, 4, 1, 28161, 8279, 2388, 596, 131, 27, 4, 1, 117631, 38218, 11603, 3032, 705, 146, 29, 4, 1, 497665, 177013, 56407, 15403, 3732, 819, 161, 31, 4, 1

Offset: 0

Author

Emeric Deutsch, Apr 01 2007

Keywords

• nonn
• tabf

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 a path is defined to be the number of its steps.

Rows 0 and 1 have one term each; row n has n-1 terms (n >= 2).

Row sums yield A002212.

Examples

			T(4,1)=4 because we have (UDUDU)UDD, (UDUDU)UDL, U(UDUDU)DD and U(UDUDU)DL (the subwords UDUDU are shown between parentheses).
Triangle starts
    1;
    1;
    3;
    9,  1;
   31,  4,  1;
  113, 19,  4,  1;
		

Links

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

Crossrefs

Cf. A002212, A052709, A026376.

Programs

Maple

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

Formula

T(n,0) = A052709(n+1).

Sum_{k=0..n-2} k*T(n,k) = A026376(n-2).

G.f.: G = G(t,z) satisfies z(1 + z - tz)G^2 - (1 - tz)G + 1 - tz = 0. G = C((1+z-tz)/(1-tz)), where C(z) = (1 - sqrt(1 - 4z))/(2z) is the Catalan function.