login
Number of walks of length n on the square lattice that start from (0,0) and do not touch the half-line {x=y, x <= 0} once they have left their starting point.
2

%I #17 Feb 26 2018 00:54:06

%S 1,4,10,40,134,536,1924,7696,28486,113944,429100,1716400,6535580,

%T 26142320,100308680,401234720,1548228166,6192912664,23999271964,

%U 95997087856,373278990004,1493115960016,5821831231160,23287324924640,91005571039516,364022284158064

%N Number of walks of length n on the square lattice that start from (0,0) and do not touch the half-line {x=y, x <= 0} once they have left their starting point.

%D Mireille Bousquet-Mélou and Gilles Schaeffer, Counting walks on the slit plane (extended abstract). Mathematics and computer science (Versailles, 2000), 101-112, Trends Math., Birkhäuser, Basel, 2000.

%H Vincenzo Librandi, <a href="/A053792/b053792.txt">Table of n, a(n) for n = 0..200</a>

%H M. Bousquet-Mélou and Gilles Schaeffer, <a href="http://www.labri.fr/Perso/~bousquet/Articles/Slitplane/PTRF/final.ps.gz">Walks on the slit plane</a>, Probability Theory and Related Fields, Vol. 124, no. 3 (2002), 305-344.

%F G.f.: ((1+4*t)^(1/4)*(1+sqrt(1-16*t^2))^(1/2))/(sqrt(2)*(1-4*t)^(3/4)).

%F Contribution from _Vaclav Kotesovec_, Oct 24 2012: (Start)

%F G.f.: 1/2*((1+4*x)/(1-4*x))^(1/4)*(1+sqrt((1+4*x)/(1-4*x))).

%F Recurrence: (n-1)*n*a(n) = 8*(n-1)*a(n-1) + 4*(8*n^2-32*n+29)*a(n-2) - 128*(n-3)*a(n-3) - 256*(n-4)*(n-3)*a(n-4).

%F a(n) ~ 2^(2*n-1/4)/(Gamma(3/4)*n^(1/4)).

%F (End)

%t CoefficientList[Series[1/2*((1+4*x)/(1-4*x))^(1/4)*(1+Sqrt[(1+4*x)/(1-4*x)]), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Oct 24 2012 *)

%Y Cf. A000108, A053791.

%K nonn

%O 0,2

%A _Mireille Bousquet-Mélou_, Mar 27 2000