A128749 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n having k ascents of length 1.

1, 0, 1, 2, 0, 1, 4, 5, 0, 1, 14, 12, 9, 0, 1, 44, 53, 25, 14, 0, 1, 150, 196, 132, 44, 20, 0, 1, 520, 777, 555, 269, 70, 27, 0, 1, 1850, 3064, 2486, 1260, 485, 104, 35, 0, 1, 6696, 12233, 10902, 6264, 2496, 804, 147, 44, 0, 1, 24602, 49096, 47955, 30108, 13600

Offset

0,4

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. An ascent in a path is a maximal sequence of consecutive U steps.

Row sums yield A002212.

Links

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

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

Formula

T(n,0) = A128750(n).

Sum_{k=0..n} k*T(n,k) = A085362(n-1).

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

Example

T(3,1)=5 because we have (U)DUUDD, (U)DUUDL, UUDD(U)D, UUD(U)DD and UUD(U)DL (the ascents of length 1 are shown between parentheses).
Triangle starts:
   1;
   0,  1;
   2,  0,  1;
   4,  5,  0,  1;
  14, 12,  9,  0,  1;
  44, 53, 25, 14,  0,  1;

Maple

eq:=z*(1+z-t*z)*G^2-(1-t*z+t*z^2-z^2)*G+1-z=0: G:=RootOf(eq, G): Gser:=simplify(series(G, z=0, 15)): for n from 0 to 11 do P[n]:=sort(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

Crossrefs

Cf. A002212, A085362, A128750.

Sequence in context: A327117 A359107 A229223 * A106579 A287318 A329020

Adjacent sequences: A128746 A128747 A128748 * A128750 A128751 A128752

Keyword

tabl,nonn

Author

Emeric Deutsch, Mar 31 2007

Status

approved