A127155 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k long ascents and long descents. A long ascent (descent) in a Dyck path is a maximal sequence of at least 2 consecutive up (down) steps.

1, 1, 1, 0, 1, 1, 0, 4, 1, 0, 10, 2, 1, 1, 0, 20, 12, 9, 1, 0, 35, 42, 47, 6, 1, 1, 0, 56, 112, 180, 64, 16, 1, 0, 84, 252, 558, 374, 148, 12, 1, 1, 0, 120, 504, 1482, 1580, 950, 200, 25, 1, 0, 165, 924, 3498, 5390, 4662, 1770, 365, 20, 1, 1, 0, 220, 1584, 7524, 15752, 18676

Offset

0,8

Comments

Row n has 1+2*floor(n/2) terms. Row sums yield the Catalan numbers (A000108).

Links

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

Chao-Jen Wang, Applications of the Goulden-Jackson cluster method to counting Dyck paths by occurrences of subwords, Dissertation, Brandeis University, 2011.

Formula

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

Example

T(4,3)=2 because we have (UU)D(UU)(DDD) and (UUU)(DD)U(DD) (here U=(1,1) and D=(1,-1); the long ascents and the long descents are shown between parentheses).
Triangle starts:
1;
1;
1,0,1;
1,0,4;
1,0,10,2,1;
1,0,20,12,9;
1,0,35,42,47,6,1;

Maple

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

Crossrefs

Cf. A000108.

Sequence in context: A284982 A089962 A363971 * A211793 A145880 A048516

Adjacent sequences: A127152 A127153 A127154 * A127156 A127157 A127158

Keyword

nonn,tabf

Author

Emeric Deutsch, Feb 27 2007

Status

approved