A370498 Number of paths from (0, 0) to (2n, 2n) in an n X n grid using only steps north, northeast and east (i.e., steps (1, 0), (1, 1), and (0, 1)) and that do not pass through diagonal points with odd coordinates.

1, 4, 60, 1204, 27724, 691812, 18198492, 496924692, 13951437804, 400212569284, 11679079547260, 345621250279284, 10347645099250060, 312857431914558244, 9538937406065229084, 292961855077076241108, 9054857076142602126636, 281439018537947499788676, 8791174819979940884130492

Offset: 0

Author

José María Grau Ribas, Feb 20 2024

Keywords

• nonn

Crossrefs

Cf. A001850, A008288, A138462.

Programs

Maple

a:= proc(n) option remember; `if`(n<2, 4^n, ((8*n-6)*(34*n^2-51*n+11)
      *a(n-1)-(n-2)*(4*n-1)*(2*n-3)*a(n-2))/(n*(4*n-5)*(2*n+1)))
    end:
seq(a(n), n=0..18);  # Alois P. Heinz, Feb 20 2024

Mathematica

A[n_, m_] :=  A[n, m] = Which[m*n == 0, 1, m == n && Mod[m, 2] == 1, 0, True, A[n - 1, m] + A[n, m - 1] + A[n - 1, m - 1]]; Table[A[2 n, 2 n], {n, 0, 45}]

Formula

a(n) = b(2*n,2*n) where b(n,0) = b(0,m) = 1, b(2n+1,2n+1) = 0 and b(n,m) = b(n-1,m-1) + b(n-1,m) + b(n,m-1) otherwise.

a(n) = ceiling((2/3)*A138462(n)).

a(n) ~ (1 + sqrt(2))^(4*n+1) / (3 * 2^(5/4) * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 14 2024

D-finite with recurrence +n*(2*n+1)*a(n) +(-70*n^2+73*n-15)*a(n-1) +(70*n^2-277*n+270)*a(n-2) -(2*n-5)*(n-3)*a(n-3)=0. - R. J. Mathar, Mar 25 2024