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

%I #21 Jul 26 2022 15:53:47

%S 0,0,1,4,15,58,232,954,4010,17156,74469,327168,1452075,6501156,

%T 29326743,133166064,608188737,2791992736,12876049123,59626721244,

%U 277150709717,1292583258866,6046985696778,28369001791034,133436435891480

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

%C 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.

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

%H G. C. Greubel, <a href="/A128714/b128714.txt">Table of n, a(n) for n = 0..1000</a>

%H E. Deutsch, E. Munarini, S. Rinaldi, <a href="http://dx.doi.org/10.1016/j.jspi.2010.01.015">Skew Dyck paths</a>, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203

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

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

%F a(n) ~ 2*5^(n+1/2)/(9*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Mar 20 2014

%F 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

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

%p 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);

%t 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 *)

%o (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

%Y Cf. A033321.

%K nonn

%O 0,4

%A _Emeric Deutsch_, Mar 30 2007