OFFSET
0,4
COMMENTS
Number of walks of length n with unit steps in all four directions (NSWE), starting at the origin and ending on the y-axis, never going below the x-axis and the end point having a positive height.
FORMULA
a(n) = n!*[x^n] (BesselI(0, 2*x)^2 + BesselI(1, 2*x)*BesselI(0, 2*x)*(1 - 1/x)).
a(n) = [x^n] (((8*x^2 + 2*x)*EllipticK(4*x) - Pi*(1 + x) + 2*EllipticE(4*x))/(4*x^2*Pi)).
a(n) = [x^n] (x*hypergeom([1,3/2,3/2], [2,2], 16*x^2) + x^2*hypergeom([3/2,3/2,2,2], [1,3,3], 16*x^2)).
a(n) = Sum_{k=0..n} (-1)^(n-k+N)*C(n-k, N)*C(n, k)*C(n+k, k), where N = floor((n-1)/2) and C = binomial.
Recurrence: a(n) = ((32*n^5 - 48*n^4 + 16*n^2)*a(n - 2) + (8*n^4 - 20*n^2)*a(n - 1))/(2*(n - 1)^2*(n - 1/2)*(n + 2)^2).
a(n) = Sum_{k=1..n} A378061(n, k).
EXAMPLE
The 16 walks of length 4: NNNN, NNNS, NNSN, NNEW, NNWE, NSNN, NENW, NEWN, NWNE, NWEN, ENNW, ENWN, EWNN, WNNE, WNEN, WENN.
MAPLE
a := n -> binomial(n, iquo(n+1, 2) - 1)^2: seq(a(n), n = 0..27);
a := proc(n) option remember; if n < 2 then n else ((32*n^5 - 48*n^4 + 16*n^2)*a(n - 2) + (8*n^4 - 20*n^2)*a(n - 1))/(2*(n - 1)^2*(n - 1/2)*(n + 2)^2) fi end:
# Alternative:
egf := BesselI(0, 2*x)^2 + BesselI(1, 2*x)*BesselI(0, 2*x)*(1 - 1/x):
ser := series(egf, x, 29): seq(n!*coeff(ser, x, n), n = 0..27);
MATHEMATICA
Array[Binomial[#, Floor[(# + 1)/2] - 1]^2 &, 28, 0] (* Michael De Vlieger, Dec 04 2024 *)
PROG
(Julia)
# Generates the walks (for illustration only).
function aCount(n::Int)
a = [""]
c = 0
for w in a
if length(w) == n
if (count('N', w) != count('S', w) && count('W', w) == count('E', w))
c += 1
# println(w)
end
else
for j in "NSEW"
u = string(w, j)
if count('N', u) >= count('S', u)
push!(a, u)
end end end end
return c
end
println([aCount(n) for n in 0:11])
CROSSREFS
KEYWORD
nonn,easy,walk
AUTHOR
Peter Luschny, Dec 03 2024
STATUS
approved