login
A128714
Number of skew Dyck paths of semilength n ending with a left step.
4
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,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 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).
LINKS
E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203
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
EXAMPLE
a(3)=4 because we have UDUUDL, UUDUDL, UUUDDL and UUUDLL.
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 *)
PROG
(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
CROSSREFS
Cf. A033321.
Sequence in context: A003126 A160156 A102052 * A007342 A017951 A326212
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Mar 30 2007
STATUS
approved