A378060 a(n) = binomial(n, floor((n-1)/2))^2.

0, 1, 1, 9, 16, 100, 225, 1225, 3136, 15876, 44100, 213444, 627264, 2944656, 9018009, 41409225, 130873600, 590976100, 1914762564, 8533694884, 28210561600, 124408576656, 418151049316, 1828114918084, 6230734868736, 27043120090000, 93271169290000, 402335398890000

Offset: 0

Author

Peter Luschny, Dec 03 2024

Keywords

• nonn
• easy
• walk

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.

Examples

			The 16 walks of length 4: NNNN, NNNS, NNSN, NNEW, NNWE, NSNN, NENW, NEWN, NWNE, NWEN, ENNW, ENWN, EWNN, WNNE, WNEN, WENN.
		

Crossrefs

Cf. A060150 (odd bisection), A337900 (even bisection), A037952, A378061.

Programs

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])

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

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).