A128714 Number of skew Dyck paths of semilength n ending with a left step.

0, 0, 1, 4, 15, 58, 232, 954, 4010, 17156, 74469, 327168, 1452075, 6501156, 29326743, 133166064, 608188737, 2791992736, 12876049123, 59626721244, 277150709717, 1292583258866, 6046985696778, 28369001791034, 133436435891480

Offset: 0

Author

Emeric Deutsch, Mar 30 2007

Keywords

• nonn

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.

Number of skew Dyck paths of semilength n and ending with a down step is A033321(n).

Examples

			a(3)=4 because we have UDUUDL, UUDUDL, UUUDDL and UUUDLL.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203

Crossrefs

Cf. A033321.

Programs

Maple

G:=(1-3*z-sqrt(1-6*z+5*z^2))/(1+z+sqrt(1-6*z+5*z^2)): Gser:=series(G,z=0,30): seq(coeff(Gser,z,n),n=0..27);

Mathematica

CoefficientList[Series[(1-3*x-Sqrt[1-6*x+5*x^2])/(1+x+Sqrt[1-6*x+5*x^2]), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *)

PARI

concat([0,0],Vec((1-3*z-sqrt(1-6*z+5*z^2))/(1+z+sqrt(1-6*z+5*z^2)) + O(z^50))) \\ G. C. Greubel, Jan 31 2017

Formula

G.f.: (1 - 3z - sqrt(1-6z+5z^2))/(1 + z + sqrt(1-6z+5z^2)).

G.f.: z(g-1)/(1-zg), where g = 1 + zg^2 + z(g-1) = (1 - z - sqrt(1-6z+5z^2))(2z).

a(n) ~ 2*5^(n+1/2)/(9*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 20 2014

D-finite with recurrence 2*(n+1)*a(n) + (-13*n+7)*a(n-1) + 2*(8*n-17)*a(n-2) + 5*(-n+3)*a(n-3) = 0. - R. J. Mathar, Jul 14 2016