A128739 Number of skew Dyck paths of semilength n having no DD's.

1, 1, 2, 5, 14, 41, 124, 386, 1230, 3992, 13150, 43856, 147796, 502530, 1721856, 5939353, 20608102, 71879003, 251876040, 886309559, 3130552258, 11095355269, 39447022648, 140645181280, 502773092420, 1801633916188, 6470373097004

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..26.

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

Formula

a(n) = A128738(n,0).

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

D-finite with recurrence 15*n*(n+1)*a(n) -n*(83*n-49)*a(n-1) +(127*n^2-263*n+90)*a(n-2) +3*(-43*n^2+117*n-20)*a(n-3) +10*(n+1)*(7*n-27)*a(n-4) +16*(n-5)*(4*n-21)*a(n-5) -64*(n-5)*(n-6)*a(n-6)=0. - R. J. Mathar, Jul 22 2022

Example

a(3)=5 because we have UDUDUD, UDUUDL, UUUDLD, UUDUDL and UUUDLL.

Maple

eq:=z^2*G^3-z*(1-z)*G^2-(1-z)*(1-3*z)*G+(1-z)^2=0: G:=RootOf(eq, G): Gser:=series(G, z=0, 35): seq(coeff(Gser, z, n), n=0..30);

Crossrefs

Cf. A128738.

Sequence in context: A159769 A159771 A159768 * A356698 A036766 A366024

Adjacent sequences: A128736 A128737 A128738 * A128740 A128741 A128742

Keyword

nonn

Author

Emeric Deutsch, Mar 31 2007

Status

approved